6.1 二元堆與優先隊列

普通隊列按到達次序取出資料；優先隊列則要在目前所有項目中取出鍵值最小（或最大）的一項。二元堆不會把全部項目排好次序，而是只維持足夠的結構，讓最小項容易取得、更新後亦只需修復一條路徑。本節採用課堂的最小堆及由 1 開始編號的陣列。

分析每個操作時，我們都分開檢查兩項不變量：樹形是否仍然完全，以及父子之間是否仍符合堆序。這個「形狀—次序」分工正是所有時間界的來源。

動機

Prim 及 Dijkstra 等演算法會反覆選取目前成本最低的候選項。若用未排序容器，加入新項可以很快，但每次找最小項都可能要掃描整個容器；若永遠把容器完全排序，找最小項雖然容易，插入時卻可能要搬動大量資料。堆選擇中間方案：它不保存完整排序，只保證根是最小項，並讓一次更新沿樹的垂直路徑修復。

優先隊列是抽象資料型別；二元堆只是其中一種實作。實際項目可以是 (暫定距離, 頂點)，由鍵值決定優先次序，payload 則隨項目一併返回。呼叫者只應依賴「返回最小鍵值」這項合約，不應把內部堆陣列當成已排序清單。

定義

定義

最小優先隊列

最小優先隊列的核心操作是：insert(x) 加入鍵值為 x 的項目；find_min() 讀取一個最小鍵值項目；delete_min() 刪除並返回一個最小鍵值項目。抽象定義行為，但沒有指定儲存方法。

定義

完全二元樹

若一棵二元樹除最後一層外每層皆滿，而最後一層由左至右連續填入、沒有空位，便稱為完全二元樹。這只是一項形狀條件，與節點鍵值無關。

本節沿用第 4 章按節點數定義樹高的約定：h 是最長根至葉路徑所含的節點數，所以空樹高度為 0，單節點樹高度為 1。深度仍按由根開始經過的邊數計算，因此根的深度為零。對含 n>0 個節點的完全二元樹，h = floor(log_2 n) + 1；等價地，2^{h-1} ≤ n ≤ 2^h - 1。根與葉之間的修復路徑最多經過 h - 1 = floor(log_2 n) 條垂直邊，因此一次 sift-up 或 sift-down 仍為 O(log n)。

定義

最小堆序

若每個非根節點的鍵值都大於或等於其父節點，樹便符合最小堆序。換句話說，每個父節點都不大於其子節點。兼具完全二元樹形狀和最小堆序的樹就是二元最小堆。

堆序只是偏序，不是完整排序。兄弟節點之間沒有大小規定，左子樹中的鍵值也不一定小於右子樹的鍵值。相同鍵值可以出現；除非另設 tie-breaker，堆亦不保證相同優先級的項目按到達次序離開。

定義

由 1 開始的陣列表示

按層次把完全二元樹存入 A[1..n]。對索引 i，

$$\operatorname{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor, \qquad \operatorname{left}(i)=2i, \qquad \operatorname{right}(i)=2i+1.$$

父索引公式只適用於 i>1；子索引不超過 n 才代表真實節點。內部節點恰為 1 至 floor(n/2)，其後全是葉節點。

完全形狀令上述公式成立：在 A[n+1] 加入項目就是填上下一個合法位置，刪除 A[n] 就是移除最後一個合法位置。判斷葉節點時，只要檢查 2i>n；即使陣列容量大於 n，超出目前大小的儲存格也不屬於堆。

定理 / 命題

定理

根最小不變量與 find_min

在非空最小堆中，根 A[1] 是全域最小鍵值。因此檢查非空後，find_min 的時間為 O(1)。

定理

單一路徑修復界

用 sift-up 修復插入、用 sift-down 修復 delete-min，兩者在含 n 項的二元堆中最壞均為 O(log n)，並會恢復完全形狀及最小堆序。

定理

Bottom-up build_heap

先把 n 個鍵值按完全樹次序放進陣列，再依次對索引 floor(n/2), floor(n/2)-1, ..., 1 執行 sift_down，所得陣列是最小堆，而總最壞時間為 O(n)。

最後一項不是把 n/2 次操作一律當成整棵樹的最大向下邊數。大部分起點貼近葉層，根本不可能走完 h - 1 = floor(log_2 n) 條邊；必須按各節點自己的最大向下邊數計費。

證明思路

任取節點 v。由根到 v 的唯一路徑鍵值不遞減，所以根鍵值不大於 v。因 v 任意，根就是全域最小；直接讀取 A[1] 不隨 n 增長，故 find_min 是常數時間。這並不代表「第二小」固定在某個陣列位置。

插入與 sift-up

先在 n+1 建立 hole，完全形狀因而保持不變。若 x 小於 hole 的父鍵值，便把父鍵值移落 hole，再把 hole 移到父位置；直至父鍵值不大於 x，或 hole 已到根，才放入 x。

INSERT(A, n, x):
    n := n + 1
    i := n
    while i > 1 and A[floor(i / 2)] > x:
        A[i] := A[floor(i / 2)]
        i := floor(i / 2)
    A[i] := x
    return n

循環開始時，除 hole 相連的邊外，其餘父子關係仍然正確。把過大的父鍵移下，只會把尚待處理的位置上移一條邊；停止時最後一條邊也符合堆序。若樹按節點數計算的高度為 h，hole 最多向上經過 h - 1 = floor(log_2 n) 條邊。

delete-min 與 sift-down

直接移走根會在完全樹的錯誤位置留下空位。因此先保存最小值，取出最後鍵值 last，縮小 n，並把根視為 hole。每步選兩個子節點中較小者；若 last 已不大於該子鍵值便停止，否則把較小子鍵移上，hole 向下移。

DELETE_MIN(A, n):
    if n = 0: report underflow
    minimum := A[1]
    if n = 1: return (minimum, 0)
    last := A[n]
    n := n - 1
    i := 1
    while 2 * i ≤ n:
        child := 2 * i
        if child + 1 ≤ n and A[child + 1] is smaller than A[child]:
            child := child + 1
        if last ≤ A[child]: break
        A[i] := A[child]
        i := child
    A[i] := last
    return (minimum, n)

必須提升較小子節點；若提升較大者，它可能立即位於較小兄弟之上而破壞堆序。循環期間，hole 下方兩棵子樹各自仍是堆，其他路徑亦沒有改動。hole 每次向下經過一條邊，最多經過 h - 1 = floor(log_2 n) 條邊，故最壞為 O(log n)。

Bottom-up 建堆

葉節點沒有子節點，本身已符合堆序。由最後一個內部節點開始倒序處理：

BUILD_HEAP(A, n):
    for i := floor(n / 2) downto 1:
        SIFT_DOWN(A, n, i)

處理 i 時，兩棵子樹索引較大，已先成為堆；SIFT_DOWN 只需修復以 i 為根的子樹。由索引反向歸納，最後索引 1 的整棵樹就是堆。

為分析運行時間，令 d 表示由某節點向下至葉節點最多經過的邊數，葉節點的 d=0。該節點最多下降 d 條邊，而最大向下邊數為 d 的節點只有 O(n/2^{d+1}) 個。因此總工作量為

$$O\!\left(n\sum_{d\ge0}\frac{d}{2^{d+1}}\right)=O(n),$$

因為按向下邊數加權的級數收斂至常數（等價地，sum d/2^d = 2）。逐項插入也可建堆，而且任何時刻都有有效堆，適合資料逐步到達的情況；但其最壞總時間是 O(n log n)。Bottom-up 方法在所有鍵值已備妥時，利用大量節點靠近葉層這項結構事實取得線性界。

從操作到優先隊列契約

空堆上的 find_min、delete_min 必須報 underflow。固定容量陣列滿時要報錯或擴容；這是儲存政策，不會改變 sift 的結構界。一次操作的最壞界也不依賴隨機輸入：新全域最小值確實可能由最後葉節點一路升至根，而很大的 last 亦可能由根降到底層。

例題詳解

例題

讀取陣列關係

對 A = [4, 9, 7, 15, 12, 11, 10]，索引 3 儲存 7；父節點在索引 1，子節點在索引 6,7，鍵值分別為 11,10。索引 4 的左子索引是 8>n，所以它是葉節點。這是最小堆，但陣列並未排序，因為 9>7。

例題

課堂追蹤：插入 14

由 [13, 21, 16, 24, 31, 19, 68, 65, 26, 32] 開始，在索引 11 開 hole。索引 5 的父鍵值 31>14，把 31 移下；hole 到索引 5 後，索引 2 的 21>14，再把 21 移下。到索引 2 時，父鍵值 13≤14，故停止並放入 14。

最終陣列是 [13, 14, 16, 24, 21, 19, 68, 65, 26, 32, 31]，只改動索引 11,5,2。

例題

課堂追蹤：刪除最小值

由 [13, 14, 16, 19, 21, 24, 68, 65, 40, 32, 31] 開始。保存 13，取出最後鍵值 31。根的子鍵為 14,16，先提升 14；下一層為 19,21，提升 19；再下一層為 65,40，而 31≤40，故把 31 放入 hole。

返回值是 13，餘下堆為 [14, 19, 16, 31, 21, 24, 68, 65, 40, 32]。

例題

課堂追蹤：bottom-up build_heap

課堂例子先放入 [15, 8, 4, 3, 1, 7, 11, 10, 2, 9, 6, 5, 12, 14, 13]。葉索引 8..15 不需處理。完成索引 7,6,5,4 後為 [15, 8, 4, 2, 1, 5, 11, 10, 3, 9, 6, 7, 12, 14, 13]；完成 3,2 後為 [15, 1, 4, 2, 6, 5, 11, 10, 3, 9, 8, 7, 12, 14, 13]；最後處理根，得到 [1, 2, 4, 3, 6, 5, 11, 10, 15, 9, 8, 7, 12, 14, 13]。

根開始 sift-down 時，左右子樹已各自成堆，這正是倒序處理的核心不變量。

操作成本總結

操作成本可直接由結構讀出：find_min 為 O(1)；insert 與 delete_min 各修復一條路徑，最壞為 O(log n)；bottom-up build_heap 按向下邊數上限加權後為 O(n)；陣列每項只佔一個位置，空間為 O(n)。

常見錯誤

• 把堆陣列當成排序結果。 堆序只限制祖先與後代，沒有比較任意相鄰項或兄弟節點。
• 混用零起點公式。 本節由 1 起點，所以父為 floor(i/2)、左子為 2i、右子為 2i+1。
• append 後不 sift-up。 append 只保持完全形狀，新項仍可能小於父節點。
• 刪根後沒有先移走最後位置。 應以最後鍵值填補根 hole 並先縮小 n，才不會破壞完全形狀。
• sift-down 提升較大子節點。 最小堆必須提升較小者，才能同時不大於兩個子節點。
• 把 build_heap 中每次 sift_down 呼叫都收費 log n。 大部分內部節點最多只可下降一兩條邊，緊確總界是 O(n)。
• 忽略空堆。 n=0 時沒有合法根，讀取或刪除前必須檢查。

總結

二元堆把完全二元樹形狀與堆序結合。完全形狀帶來對數高度及緊密的層序陣列；最小堆序把全域最小值固定於根。插入在最後位置開 hole 並向上修復；delete-min 移走根、以最後鍵值建立根 hole，再沿較小子節點向下修復。兩者各走一條路徑。Bottom-up build_heap 由最後內部節點倒序開始，因向下邊數上限較大的節點數量以幾何速度減少，所以總時間是線性。這些性質令堆成為有效的最小優先隊列實作。

練習

思考檢查

一個大小為 14、由 1 開始編號的堆中，索引 11 的父索引是甚麼？索引 7 有哪些有效子索引？

套用索引公式後，逐一與 n 比較。

思考檢查

由 [3, 8, 5, 12, 10, 9] 插入 4。修復向哪個方向移動？最終陣列是甚麼？

先把新項 append 至下一個合法位置，再只與祖先比較。

思考檢查

delete-min 的 sift-down 為何必須提升兩個子節點中較小的一個？

說明提升後，新父節點與兩個子節點必須滿足的關係。

思考檢查

即使一次 sift_down 可用 O(log n)，為何 bottom-up build_heap 的總時間仍是 O(n)？

按起點的向下邊數上限 d 把節點分組計費。

答案與解答

解答 · 1. 陣列關係

索引 11 的父為 floor(11/2)=5。索引 7 的候選子索引為 14,15；因堆大小是 14，只有 14 有效。

解答 · 2. 插入追蹤

把 4 放在新索引 7。其父索引 3 的鍵值是 5，所以把 5 移下，hole 上移到 3。新父索引 1 的鍵值是 3；因 3≤4，停止。這是 sift-up，最終陣列為 [3, 8, 4, 12, 10, 9, 5]。

解答 · 3. 較小子節點

設子鍵值 a≤b。提升 a 後，新父鍵值不大於兄弟 b，兩條父子邊都合法；若 a 嚴格小於 b 時提升 b，便會立即令 b 位於 a 之上，違反最小堆序。

解答 · 4. 線性建堆

若 d 是由某節點向下至葉節點最多經過的邊數，該節點最多下降 d 條邊，而最大向下 邊數為 d 的節點只有 O(n/2^{d + 1}) 個。總費用為 O(n sum d/2^{d + 1})=O(n)， 因該級數為常數。O(n log n) 的寬鬆估算錯把每個內部節點都當成可經過整棵樹的最大 向下邊數。