就地排序演算法：堆積排序

筆記／就地排序演算法：堆積排序

堆積排序（heap­sort）是一個能在 $O(1+nL(n))$ 時間內排序 $n$ 個元素的排序演算法，其中 $L(n) = \lceil \log_2 (n \varplus 1) \rceil \period$本文簡述堆積排序的步驟及其時間複雜度的分析。

$ \gdef\twodots{\mathinner{\ldotp\ldotp} \allowbreak} $

1　準備工作

設 $A[0 \twodots n \varminus 1]$ 為一陣列。對任意整數 $a \jcomma b \comma$我們定義 \[\begin{split}[a \twodots b] = \{k \in \ZZ: a \leq k \leq b\} \period\end{split}\]

對任意非負整數 $k \comma$設 $L(k) = \lceil \log_2 (k \varplus 1) \rceil \period$

1.1　最大堆積性質

對任意整數 $m \in \{0 \cm 1 \cm \ldots \cm n\} \comma$子陣列 $A[0 \twodots m \varminus 1]$ 稱為 $A[0 \twodots n \varminus 1]$ 的一個前綴。

給定前綴 $A[0 \twodots m \varminus 1]$ 與一索引值 $i \in [0 \twodots m \varminus 1] \comma$若下列敘述成立，則我們稱 $i$ 在前綴 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質（maximum-heap prop­er­ty）：

  1. 若 $2i + 1 < m \comma$則 $A[2i \varplus 1] \leq A[i] \period$
  2. 若 $2i + 2 < m \comma$則 $A[2i \varplus 2] \leq A[i] \period$

1.2　最大堆積

若每個索引值 $i \in [0 \twodots m \varminus 1]$ 均在 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質，則我們稱前綴 $A[0 \twodots m \varminus 1]$ 為一最大堆積（maximum heap）。

可以注意到若 $A[0 \twodots m \varminus 1]$ 為最大堆積且 $m \geq 1 \comma$則 $A[0]$ 為 $A[0 \twodots m \varminus 1]$ 中的最大值。

2　演算法

2.1　向後插入

演算法 A（向後插入） 給定前綴 $A[0 \twodots m \varminus 1]$ 與一索引值 $i \in [0 \twodots m \varminus 1] \comma$其中 $[i \varplus 1 \twodots m \varminus 1]$ 中的索引值在演算法執行前均在前綴 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質；演算法 A 會將此前綴重排，使 $[i \twodots m \varminus 1]$ 中的索引值均在此前綴中滿足最大堆積性質。

  1. 設 $j \gets i$ 與 $k \gets i \period$
  2. 若 $2j + 1 < m$ 且 $A[2j \varplus 1] > A[k] \comma$則設 $k \gets 2j + 1 \period$
  3. 若 $2j + 2 < m$ 且 $A[2j \varplus 2] > A[k] \comma$則設 $k \gets 2j + 2 \period$
  4. 若 $j \neq k \comma$則交換 $A[\mkern2muj] \leftrightarrow A[k] \comma$接著設 $j \gets k \comma$並回到步驟 2；否則終止演算法。

正確性　首先我們說明以下條件在首次進入步驟 2 與每次離開步驟 4 時均成立：

  1. $j = k \period$
  2. $[i \twodots m \varminus 1]$ 中除了 $j$ 以外的索引值均滿足最大堆積性質。

我們驗證如下：

可以注意到離開步驟 4 時，演算法會終止的充要條件為進入步驟 4 時 $j = k$ 成立，此時索引值 $j$ 必須滿足最大堆積性質。故由 (b) 可知演算法終止時 $[i \twodots m \varminus 1]$ 中的索引值均滿足最大堆積性質。

最後我們確認演算法必定終止。由於每次執行步驟 2―4 後，若有跳回步驟 2，則 $j$ 至少會變為 $2j + 1 \comma$且進入步驟 2 時必須有 $j \leq m - 1 \comma$故演算法必定在有限步內結束。至此演算法 A 的正確性得證。

時間複雜度　對非負整數 $t \comma$設 $j^{(t)}$ 為第 $t + 1$ 次進入步驟 2 時 $j$ 的值。若執行一次步驟 2―4 後有跳回步驟 2，則 $j$ 至少會變為 $2j + 1 \comma$即 $j^{(t)} \geq 2j^{(t-1)}+1 \period$若步驟 2 共執行 $T$ 次，則對任意 $0 \leq t \leq T-2$ 均有 \[\begin{split}\frac{j^{(t+1)}+1}{j^{(t)}+1} \geq \frac{(2j^{(t)} + 1)+1}{j^{(t)}+1} = 2 \period\end{split}\] 若 $T \geq 2 \comma$則由 $j^{(0)} = i$ 與 $j^{(T-1)} \leq m - 1$ 可知 \[\begin{split}T &\leq 1 + \biggl\lfloor\log_2\biggl(\frac{m}{i+1}\biggr)\biggr\rfloor \\[2ex] &\leq 1 + L\.(m) - L\.(i + 1)\period\end{split}\] 故演算法 A 的時間複雜度為 $O(1 + L(m) - L(i \varplus 1)) \period$

2.2　建造堆積

演算法 B（建造堆積） 給定陣列 $A[0 \twodots n \varminus 1]$，演算法 A 會將其重排為一最大堆積。

  1. 設 $i \gets \lfloor n/2 \rfloor - 1 \comma$並跳至步驟 4。
  2. 對整個陣列 $A[0 \twodots n \varminus 1]$ 與索引值 $i$ 執行演算法 A（向後插入）。
  3. 設 $i \gets i - 1 \period$
  4. 若 $i \geq 0 \comma$則回到步驟 2；否則終止演算法。

正確性　首次進入步驟 2 時，$[i \varplus 1 \twodots n \varminus 1]$ 中的索引值均滿足最大堆積性質（因為此時 $i = \lfloor n/2 \rfloor - 1$ 且 $2(i \varplus 1) + 1 \geq n \rparen \mkern-9mu \period$

若每次進入步驟 2 時，$[i \varplus 1 \twodots n \varminus 1]$ 中的索引值均滿足最大堆積性質，則由演算法 A 的正確性可知離開步驟 2 時，$[i \twodots n \varminus 1]$ 中的索引值滿足最大堆積性質。

由此可知演算法結束時，$[0 \twodots n \varminus 1]$ 中的索引值均滿足最大堆積性質，即正確性得證。

時間複雜度　可知步驟 2 以外花費的總時間為 $O(1 + n) \comma$以下我們考慮步驟 2 花費的總時間。對每個索引值 $i \comma$步驟 2 需要花費 $O(1 + L(n) - L(i \varplus 1))$ 的時間。由 \[\begin{split} &\sum_{i=0}^{\lfloor n/2 \rfloor - 1} (1 + L(n) - L(i \varplus 1)) \\ &\leq \sum_{k=0}^{L(n)-1} \sum_{i=2^k-1}^{2^{k+1}-2} (1 + L(n) - L(i \varplus 1)) \\ &= \sum_{k=0}^{L(n)-1} 2^k (1 + L(n) - (k \varplus 1)) \\ &= \sum_{k=0}^{L(n)-1} 2^k (L(n) - k) \\ &= \sum_{h=1}^{L(n)} 2^{L(n) - h}h \\ &\leq 2^{L(n)} \sum_{h \geq 1} \frac{h}{2^h} \\ &\leq 2n \cdot 2 \comma \end{split}\] 可知步驟 2 花費的總時間為 $O(1 + n) \comma$故演算法 B（建造堆積）的時間複雜度為 $O(1 + n) \period$

2.3　拆除堆積

演算法 C（拆除堆積） 給定最大堆積 $A[0 \twodots n \varminus 1]$，演算法 C 會將其重排為由小到大排列。

  1. 設 $m \gets n - 1 \comma$並跳至步驟 5。
  2. 交換 $A[0] \leftrightarrow A[m] \comma$並設 $i \gets 0 \period$
  3. 對前綴 $A[0 \twodots m \varminus 1]$ 與索引值 $i$ 執行演算法 A（向後插入）。
  4. 設 $m \gets m - 1 \period$
  5. 若 $m \geq 1 \comma$則回到步驟 2；否則終止演算法。

正確性　首次進入步驟 2 時，$A[0 \twodots m]$ 為最大堆積，故在交換 $A[0] \leftrightarrow A[m]$ 並進入步驟 3 後，$A[m]$ 即為 $A[0 \twodots m]$ 中的最大值，且在前綴 $A[0 \twodots m \varminus 1]$ 中除了 0 以外的索引值均滿足最大堆積性質。

若進入步驟 3 時，前綴 $A[0 \twodots m \varminus 1]$ 中除了 0 以外的索引值均滿足最大堆積性質，則由演算法 A 的正確性可知離開步驟 3 時，前綴 $A[0 \twodots m \varminus 1]$ 會形成最大堆積。

由此可知演算法結束時，對任意 $i \in [0 \twodots n \varminus 1] \comma$$A[i]$ 均為 $A[0 \twodots i]$ 的最大值。故正確性得證。

時間複雜度　步驟 3 以外花費的總時間為 $O(1 + n) \comma$且步驟 3 花費的總時間為 $O(nL(n)) \comma$故時間複雜度為 $O(1 + nL(n)) \period$

2.4　堆積排序

利用演算法 B（建造堆積）、演算法 C（拆除堆積）即可排序陣列。

演算法 D（堆積排序） 給定陣列 $A[0 \twodots n \varminus 1]$，演算法 D 會將其重排為由小到大排列。

  1. 對陣列 $A[0 \twodots n \varminus 1]$ 執行演算法 B（建造堆積）。
  2. 對陣列 $A[0 \twodots n \varminus 1]$ 執行演算法 C（拆除堆積）。

正確性　由演算法 B、C 的正確性得證。

時間複雜度　步驟 1 花費時間為 $O(1 + n) \comma$且步驟 2 花費時間為 $O(1 + nL(n)) \comma$故時間複雜度為 $O(1 + nL(n)) \period$

3　程式碼實作

以下為 Python 的實作：

  1. 函式 sift_down 執行向後插入。
  2. 函式 build_heap 執行建造堆積。
  3. 函式 destroy_heap 執行拆除堆積。
  4. 函式 heapsort 執行堆積排序。
from collections.abc import Sequence

def sift_down(A: Sequence, m: int, i: int) -> None:
    ok = False
    j, k = i, i
    while not ok:
        if j * 2 + 1 < m and A[j * 2 + 1] > A[k]:
            k = j * 2 + 1
        if j * 2 + 2 < m and A[j * 2 + 2] > A[k]:
            k = j * 2 + 2
        if j != k:
            A[j], A[k] = A[k], A[j]
            j = k
        else:
            ok = True

def build_heap(A: Sequence) -> None:
    n = len(A)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(A, n, i)

def destroy_heap(A: Sequence) -> None:
    n = len(A)
    for m in range(n - 1, 0, -1):
        A[0], A[m] = A[m], A[0]
        sift_down(A, m, 0)

def heapsort(A: Sequence) -> None:
    build_heap(A)
    destroy_heap(A)

參考資料

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, third edition, 2009.