不占空間的排序演算法：堆積排序

2023-10-06

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

備註　以下我們所使用的漸近記號採用較嚴格的定義：若我們稱一演算法在輸入大小為 $n$ 時的花費時間為 $O(\.T(n)) \comma$則代表存在一正數 $C \comma$使得在任意輸入大小為 $n$ 的狀況下該演算法的執行時間皆不超過 $C \cdot T(n) \period$

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}\]

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 property）：

若 $2i + 1 < m \comma$則 $A[2i \varplus 1] \leq A[i] \period$
若 $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$其中 $\sbrack{i \varplus 1 \twodots m \varminus 1}$ 中的索引值在演算法執行前均在前綴 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質，則演算法 A 會將此前綴重排，使 $\sbrack{i \twodots m \varminus 1}$ 中的索引值均在此前綴中滿足最大堆積性質。

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

正確性　首先我們驗證每次進入步驟 2 與離開步驟 4 時，以下敘述恆成立：

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

首次進入步驟 2 時即有 $k = i = j \period$接著進入步驟 4 時若有 $j \neq k \comma$則我們會設 $k \gets j \comma$故 (a) 成立。

首次進入步驟 2 時，由於 $j = i$ 且 $\sbrack{i \varplus 1 \twodots m \varminus 1}$ 中的索引值均滿足最大堆積性質，故 (b) 成立。由 (a) 可知每次經過步驟 2、3 後，進入步驟 4 時有 \[\begin{split}A[k] \in \argmax_{k'\.\in\.K} A[k'] \comma\end{split}\] 其中 \[\begin{split}K = \cbrackc2{j, 2j \varplus 1, 2j \varplus 2} \cap [0 \twodots m \varminus 1] \period\end{split}\] 因此在步驟 4 中交換 $A\sbrackc2{j} \leftrightarrow A\sbrack{k}$ 後，索引值 $j$ 會滿足最大堆積性質，即 $[i \twodots m \varminus 1]$ 中除了 $k$ 以外的索引值均滿足最大堆積性質。故步驟 4 最後設 $j \gets k$ 之後，(b) 即成立。

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

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

時間複雜度　對非負整數 $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\;\blacksquare$

2.2　建造堆積

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

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

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

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

由此可知演算法結束時，$\sbrack{0 \twodots m \varminus 1}$ 中的索引值均滿足最大堆積性質，即正確性得$\textrm{證。}\mkern6mu\blacksquare$

時間複雜度　可知步驟 2 以外花費的總時間為 $O(1 + n) \comma$以下我們考慮步驟 2 花費的總時間。設存在一常數 $C \comma$使每次執行步驟 2 時，花費時間不超過 \[\begin{split}C(1 + L(n) - L(i \varplus 1)) \comma\end{split}\] 其中 $i \in \{\lfloor n/2 \rfloor \varminus 1 \cm \ldots \cm 1 \cm 0\} \period$對任意非負整數 $k \comma$若 \[\begin{split}2^k \varminus 1 \leq i < 2^{k+1} \varminus 1 \comma\end{split}\] 則我們有 $L(i \varplus 1) = k + 1 \period$因此步驟 2 花費的總時間不會超過 \[\begin{split} T &= C \cdot \sum_{i=0}^{\lfloor n/2 \rfloor - 1} (1 + L(n) - L(i \varplus 1)) \\ &\leq C \cdot \sum_{k=0}^{L(n)-1} \sum_{i=2^k-1}^{2^{k+1}-2} (1 + L(n) - L(i \varplus 1)) \\ &= C \cdot \sum_{k=0}^{L(n)-1} 2^k (1 + L(n) - (k \varplus 1)) \\ &= C \cdot \sum_{k=0}^{L(n)-1} 2^k (L(n) - k) \\ &= C \cdot \sum_{h=1}^{L(n)} 2^{L(n) - h}h \\ &\leq C \cdot 2^{L(n)} \sum_{h \geq 1} \frac{h}{2^h} \\ &\leq C \cdot 2n \cdot 2 \comma \end{split}\]

故時間複雜度為 $O(n) \period\;\blacksquare$

2.3　拆除堆積

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

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

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

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

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

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

2.4　堆積排序

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

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

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

正確性　由演算法 B、C 的正確性得$\textrm{證。}\mkern6mu\blacksquare$

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

3　程式碼實作

以下為 Python 的實作：

函式 sift_down 執行向後插入。
函式 build_heap 執行建造堆積。
函式 destroy_heap 執行拆除堆積。
函式 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)

參考資料

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

不占空間的排序演算法：堆積排序

1 準備工作

1.1 最大堆積性質

1.2 最大堆積

2 演算法

2.1 向後插入

2.2 建造堆積

2.3 拆除堆積

2.4 堆積排序

3 程式碼實作