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

2023-10-06

堆積排序（heapsort）是一個能在 $O(nL(n))$ 時間內排序 $n$ 個元素的排序演算法，其中 $L(n) = \lceil \log_2 (n \varplus 1) \rceil \period$

由於堆積排序是一種就地（in-place）演算法，且在基於比較的計算模型下具有最佳的時間複雜度，使其成為排序演算法中的一個通用選擇。

本文簡介堆積排序的步驟，並證明其正確性及分析其時間複雜度。

術語

本文中，我們會使用一個固定的整數陣列 $A[0 \twodots n \varminus 1] \period$此外，對任意整數 $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$ 表示 $k$ 以二進位表示時所需的位數，即其位元寬度（bit width）。我們有 \[\begin{split}L(k) = \begin{cases}0 & \when k = 0 \\ 1 \varplus \lfloor \log_2 k \rfloor & \when k \geq 1 \end{cases} \period\end{split}\]

最大堆積性質

對任意整數 $m \in \{0 \cm 1 \cm \ldots \cm n\} \comma$子陣列 $A[0 \twodots m \varminus 1]$ 稱為 $A[0 \twodots n \varminus 1]$ 的一個前綴，並設 \[\begin{split}C_m(i) = \{2i \varplus 1, 2i \varplus 2\} \cap [0 \twodots m \varminus 1] \period\end{split}\]

給定前綴 $A[0 \twodots m \varminus 1]$ 與一索引值 $i \in [0 \twodots m \varminus 1] \comma$若對所有 $j \in C_m(i)$ 均有 $A[\mkern2muj] \leq A[i] \comma$則我們稱索引值 $i$ 在前綴 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質（maximum-heap property）。

最大堆積

若每個 $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]$ 中的最大值。

演算法

向後插入

演算法 A（向後插入） 設 $m \in [1 \twodots n] \comma i \in [0 \twodots m \varminus 1] \comma$並假設 $[i \varplus 1 \twodots m \varminus 1]$ 中的每個索引值均在前綴 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。

以下的 $\textsc{SiftForward}(A, m, i)$ 會將前綴 $A[0 \twodots m \varminus 1]$ 重排，使 $[i \twodots m \varminus 1]$ 中的每個索引值均在前綴 $A[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。

備註　也就是說，不破壞 $[i \varplus 1 \twodots m \varminus 1]$ 中索引值在此前綴中的最大堆積性質，且讓 $i$ 在此前綴中也具有最大堆積性質。

$\textsc{SiftForward}(A, m, i) \jcolon$

設 $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$
若 $j \neq k \comma$則交換 $A[\mkern2muj] \leftrightarrow A[k] \comma$接著設 $j \gets k \comma$並回到步驟 2；否則終止演算法。

正確性　我們將首次進入步驟 2 時 $j \jcomma k$ 的值分別記作 $j_0 \jcomma k_0 \comma$且將 $A[0 \twodots n \varminus 1]$ 此時的狀態記作 $A_0[0 \twodots n \varminus 1] \semicolon$將第 $t$ 次離開步驟 4 時 $j \jcomma k$ 的值分別記作 $j_t \jcomma k_t \comma$且將 $A[0 \twodots n \varminus 1]$ 此時的狀態記作 $A_t[0 \twodots n \varminus 1] \period$

對任意正整數 $t \comma$若步驟 2―4 執行至少 $t + 1$ 次，則有 $j_t = k_t \geq 2j_{t-1} + 1 \period$由此可知演算法會在有限時間內終止；以下假設步驟 2―4 共執行 $T$ 次。

接著我們說明對所有 $t \in [0 \twodots T \varminus 1] \comma$下列敘述成立：

在 $[i \twodots m \varminus 1]$ 中除了 $j_t$ 以外的索引值均在 $A_t[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。

我們證明如下。

首先，由演算法的前置條件，可知在 $[i \twodots m \varminus 1]$ 中除了 $j_0 = i$ 以外的索引值均在 $A_0[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。
接著假設 $[i \twodots m \varminus 1]$ 中除了 $j_{t-1}$ 以外的值均在 $A_{t-1}[0 \twodots m \varminus 1]$ 中滿足最大堆積性質，其中 $1 \leq t \leq T \varminus 1 \period$我們說明在 $[i \twodots m \varminus 1]$ 中除了 $j_t$ 以外的值均在 $A_t[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。

當第 $t$ 次執行步驟 2、3 時，會找到一個 \[\begin{split}k \in \{\mkern2muj_{t-1}\} \cup C_m(\mkern2muj_{t-1})\end{split}\] 使 $A[k]$ 最大；此時的 $k$ 即為 $k_t \period$

而在接下來的步驟 4 中，會交換 $A[\mkern2muj_{t-1}] \leftrightarrow A[k_t] \period$也就是說，由 $k_t = j_t$ 我們有：\[\begin{split}A_t[p] = \begin{cases}A_{t-1}[\mkern2muj_t] & \when p = j_{t-1} \\ A_{t-1}[\mkern2muj_{t-1}] & \when p = j_t \\ A_{t-1}[p] & \when p \notin \{\mkern2muj_{t-1}, j_t\}\end{cases} \period\end{split}\]第 $t$ 次步驟 4 的交換至多會影響 $j_{t-2} \jcomma j_{t-1} \jcomma j_t$ 這三個值是否對 $A_t[0 \twodots m \varminus 1]$ 滿足最大堆積性質。
- 由於 \[\begin{split}A_t[\mkern2muj_{t-2}] = A_{t-1}[\mkern2muj_{t-1}] \geq A_{t-1}[\mkern2muj_t] = A_t[\mkern2muj_{t-1}] \comma\end{split}\]故 $j_{t-2}$ 對 $A_t[0 \twodots m \varminus 1]$ 滿足最大堆積性質。
- 由交換的規則可知 $A_{t-1}[\mkern2muj_t] = A_{t-1}[k_t] \geq A_{t-1}[\mkern2muj_{t-1}] \comma$因而有 \[\begin{split}A_t[\mkern2muj_{t-1}] = A_{t-1}[\mkern2muj_t] \geq A_{t-1}[\mkern2muj_{t-1}] = A_t[\mkern2muj_t] \comma\end{split}\]即 $j_{t-1}$ 對 $A_t[0 \twodots m \varminus 1]$ 滿足最大堆積性質。
至此可知 $[i \twodots m \varminus 1]$ 中除了 $j_t$ 以外的值均在 $A_t[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。

目前為止的推論已足以確認在 $[i \twodots m \varminus 1]$ 中除了 $j_{T-1}$ 以外的索引值均在 $A_{T-1}[0 \twodots m \varminus 1]$ 中滿足最大堆積性質。而由於第 $T$ 次執行步驟 2―4 後就會終止演算法，故 $j_{T-1}$ 會在 $A_{T-1}[0 \twodots m \varminus 1]$ 中滿足最大堆積性質，且有 $j_T = k_T = j_{T-1}$ 與 $A_T[0 \twodots m \varminus 1] = A_{T-1}[0 \twodots m \varminus 1] \period$因此 $[i \twodots m \varminus 1]$ 中的值均在 $A_T[0 \twodots m \varminus 1]$ 中滿足最大堆積性質，演算法 A 的正確性得證。

時間複雜度　我們利用步驟 2―4 的執行次數 $T$ 分析演算法 A 的時間複雜度。我們有 $j_{t+1} \geq 2j_t+1 \comma$故 \[\begin{split}\frac{j_{t+1} + 1}{j_t + 1} \geq \frac{(2j_t + 1)+1}{j_t + 1} = 2 \period\end{split}\] 由 $j_0 = i$ 可知 $j_t \geq 2^t(i \varplus 1) - 1 \period$由 $j_{T-1} \leq m - 1$ 可知 $2^{T-1}(i \varplus 1) - 1 \leq m - 1 \comma$即 \[\begin{split}T &\leq 1 + \biggl\lfloor\log_2\biggl(\frac{m}{i \varplus 1}\biggr)\biggr\rfloor \\[2ex] &\leq 1 + L(m) - L(i \varplus 1)\period\end{split}\] 故演算法 A 的時間複雜度為 $O(1 + L(m) - L(i \varplus 1)) \period$

建造堆積

演算法 B（建造堆積） 給定陣列 $A[0 \twodots n \varminus 1] \comma$以下的 $\textsc{BuildHeap}(A, n)$ 會將其重排為一最大堆積。

$\textsc{BuildHeap}(A, n) \jcolon$

設 $i \gets \lfloor n/2 \rfloor - 1 \comma$並跳至步驟 4。
根據演算法 A 執行 $\textsc{SiftForward}(A, n, i) \period$
設 $i \gets i - 1 \period$
若 $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(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(n) \comma$故演算法 B（建造堆積）的時間複雜度為 $O(n) \period$

拆除堆積

演算法 C（拆除堆積） 給定最大堆積 $A[0 \twodots n \varminus 1] \comma$以下的 $\textsc{DestroyHeap}(A, n)$ 會將其重排為由小到大排列。

$\textsc{DestroyHeap}(A, n) \jcolon$

設 $m \gets n - 1 \comma$並跳至步驟 5。
交換 $A[0] \leftrightarrow A[m] \comma$並設 $i \gets 0 \period$
根據演算法 A 執行 $\textsc{SiftForward}(A, m, i) \period$
設 $m \gets m - 1 \period$
若 $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(n) \comma$且步驟 3 花費的總時間為 $O(nL(n)) \comma$故時間複雜度為 $O(nL(n)) \period$

堆積排序

有了前面的準備工作，現在我們利用演算法 B、C 即可排序陣列。

演算法 D（堆積排序） 給定陣列 $A[0 \twodots n \varminus 1] \comma$以下的 $\textsc{Heapsort}(A, n)$ 會將其重排為由小到大排列。

$\textsc{Heapsort}(A, n) \jcolon$

根據演算法 B 執行 $\textsc{BuildHeap}(A, n) \period$
根據演算法 C 執行 $\textsc{DestroyHeap}(A, n) \period$

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

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

程式碼實作

以下為 Python 的實作。

from collections.abc import MutableSequence

def sift_forward(A: MutableSequence, m: int, i: int) -> None:
    j = i
    k = i
    done = False
    while not done:
        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:
            done = True

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

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

def heapsort(A: MutableSequence) -> 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.