第 9 章　累堆結構

最後一節的回報很具體：用費氏累堆，第 6 章的 Prim 最小成本生成樹與 Dijkstra 最短路徑都獲得改善 —— 這正是第 6 章兩度預告過的事。

「令 $x$ 為最小-最大累堆中任一節點。如果 $x$ 位在最小階層，則 $x$ 中的元素是在以 $x$ 為根的子樹的所有元素中具有最小鍵值者。稱此為最小節點（min node）。同樣地，如果 $x$ 位在最大階層，則 $x$ 中的元素是在以 $x$ 為根的子樹的所有元素中具有最大鍵值者。稱此為最大節點（max node）。」

「每當 delete_min 的 for 迴圈重複執行一次，它完成一定量的工作。而且在每次執行時（可能最後一次除外），$i$ 向下移動兩階層。因最小-最大累堆為完整二元樹，heap 有 $O(\log n)$ 階層。所以，delete_min 的複雜度為 $O(\log n)$。」

「刪除最大鍵值元素的函數與 delete_min 類似。它的演算法設計留作習題。」

「deap 是一個雙向累堆，它支援雙向優先權佇列的運算，如插入，刪除最小的元素，和刪除最大的元素。就像最小-最大累堆一樣，在 deap 上這些運算所需時間為對數的函數。但是，deap 較快一個常數因子，且其演算法較簡單。」

定義：deap 是一完整二元樹，它是空的或滿足下列特性：

1. 根不包含元素。
2. 左子樹為最小累堆。
3. 右子樹為最大累堆。
4. 如果右子樹不是空的，則令 $i$ 為左子樹中的任一節點。令 $j$ 為右子樹中相對的節點。如果這樣的節點 $j$ 不存在，則令 $j$ 為右子樹中與 $i$ 的父節點相對的節點。在節點 $i$ 中的鍵值小於或等於節點 $j$ 中的鍵值。

「其方法是首先將從最小累堆的根節點刪除元素轉換成從最小累堆的葉節點位置刪除元素。這個工作沿著最小累堆中從根到葉節點的路徑進行，以保証最小累堆的特性在累堆的先前各階層中都是符合的。這個處理的結果是將原先在最小累堆根節點的空的位置移到葉節點 $p$。這個葉節點隨後以元素 $t$ 填入，這個元素原來在 deap 的最後一個位置。將 $t$ 插入最小累堆的位置 $p$ 以 deap_insert 來完成」，但 max_partner(i) 的定義改為……

課本的具體追蹤：「要填入這個空位，沿著從根到葉節點的路徑移動。在每次移動之前，我們將目前這個節點的子節點中較小的元素放到目前的節點中。然後移到被移動的節點原來佔用的位置。在此例中，首先將 8 移到節點 2。然後將 9 移到 8 原來佔用的節點。現在，我們有一個空的葉節點，然後將 20 插入這個節點。比較 20 和在其最大同伴之內的鍵值 40。因 $20 \lt 40$，則不需要交換，並且將 20 插入以空的位置開始的最小累堆中。」

「我們可以很容易地驗証 deap_delete_min 正確地工作，不論 deap 的最後位置是在最小或最大累堆中。因 deap 的高度為 $O(\log n)$，其複雜度為 $O(\log n)$。deap_delete_max 運算以類似的方法執行。」

「在前一節中我們將雙向優先權佇列的定義擴充，使其容許刪除最大元素和刪除最小元素運算。本節我們討論另一種擴充。假設除了一般的優先權佇列運算以外，還需要有結合（Combine）運算。這個運算將兩個優先權佇列結合成一個優先權佇列。」

一個很具體的應用場景：「當有一個優先權佇列的伺服程式（server）當掉時為這種結構的一種應用。此時必須將它的優先權佇列與另一仍正常工作的伺服程式之優先權佇列結合。」

「擴充二元樹（extended binary tree）為二元樹，其所有的空的二元子樹以方形節點取代。……在擴充二元樹中的方形節點稱為外部節點（external node）。二元樹原有的（圓形）節點稱為內部節點（internal node）。」

「令 $x$ 為擴充二元樹的節點。令 left_child(x) 與 right_child(x) 分別表示內部節點 $x$ 的左子節點與右子節點。定義 shortest(x) 為從 $x$ 到一外部節點的最短路徑之長度。我們很容易地可以發現 shortest(x) 滿足下列的遞迴公式：」

令 $x$ 為有 $n$ 個（內部）節點的左傾樹之根節點。

(a) $n \ge 2^{\textit{shortest}(x)} - 1$
(b) 最右邊的根到外部節點路徑為最短的根到外部節點路徑。其長度為 $\textit{shortest}(x)$。

證明 (a)：「根據 shortest(x) 的定義，在左傾樹第一個 shortest(x) 階層不會有外部節點。因此，左傾樹至少有」

證明 (b)：「直接由左傾樹的定義，可知這個公設成立。□」

「最小左傾樹（min-leftist tree）（或最大左傾樹，max-leftist tree）為左傾樹，其中每一節點的鍵值不大於（不小於）其子節點（如果有）中的鍵值。換言之，最小（最大）左傾樹是一種也是最小（最大）樹的左傾樹。……插入，刪除最小元素（刪除最大之元素）以及結合等運算，在使用最小（最大）左傾樹時，可以在對數函數時間內完成。」

1. 選根：if ((*a)->data.key > (*b)->data.key) SWAP(*a,*b,temp); —— 保證 *a 是鍵值較小的那一棵。
2. 遞迴：min_union(&(*a)->right_child, b); —— 只往右邊遞迴，這就是為什麼複雜度受限於兩條最右路徑。
3. 修復左傾性質：若左子樹的 shortest 比右子樹小就交換左右，然後更新 shortest。這一步是「左傾」得以維持的全部機制。

「二系累堆是一種資料結構，它支援的運算和左傾樹所支援的運算相同（即插入，刪除最小或最大元素，以及結合）。在左傾樹中各別運算可以在 $O(\log n)$ 時間內完成，與這不同的是，在二系累堆上執行的一些運算可能需要 $O(n)$ 時間。如果我們分攤昂貴運算的部分成本到不昂貴的運算上，則個別運算的分攤複雜度可能是 $O(1)$ 或 $O(\log n)$，視運算的種類而定。」

「假設我們可以証明無論插入和刪除最小元素運算執行的順序為何，我們可以用每一插入的分攤成本不超過 2，且每一刪除最小元素的分攤成本不超過 6 的方式來算成本。這使得我們可以聲明任何插入／刪除最小元素之順序的實際成本不會超過 $2i + 6d$，其中 $i$ 和 $d$ 分別為在順序中插入和刪除最小元素運算之次數。」

「假設刪除最小元素的實際成本不大於 10，而插入的實際成本不大於 1。根據實際成本，我們可推論順序之成本不大於 $i + 10d$。結合這兩個上限，可得到 $\min\{2i+6d,\ i+10d\}$ 為順序成本之上限。」

「因此，使用分攤成本表示法，我們可以獲得一連串的運算的複雜度更精密的上限值。我們將以成本分攤表示法來証明雖然在二系累堆上個別的刪除運算可能很昂貴，但二系累堆運算的任何順序之成本實際上非常小。」

「正如累堆和左傾樹一般，二系累堆也有兩種：最小和最大。最小二系累堆（min-binomial heap）為最小樹之集合，而最大二系累堆為最大樹之集合。本節將只討論最小二系累堆。它將以 B-累堆表示。」

「使用 B-累堆，一個插入和一個結合運算可以在 $O(1)$ 實際和分攤時間內完成，而一個刪除最小元素運算則在 $O(\log n)$ 分攤時間內完成。」

「一個節點的所有子節點形成一個雙向鏈結環形串列，而此節點指向其中的任一個子節點。此外，構成 B-累堆的最小樹之根節點也連接形成一個雙向鏈結環形串列。B-累堆則以一個指向有最小鍵值的最小樹之根節點的指標表示。」

刪除最小元素後，它的子節點全部變成新的最小樹。接著要反覆結合分支度相同的最小樹，直到所有最小樹的分支度都不相同為止。

課本的追蹤：「的最小樹變成根節點為 7 的最小樹之子樹。現在最小樹的集合如圖 9.18。在此集合中有三個最小樹的分支度為 2，如果選擇根節點 7 和 3 的兩個來合併，結果的最小樹之集合在圖 9.19。因此集合中的最小樹的分支度都不相同，最小樹結合過程結束。」

「當我們完成了結合最小樹，將其根點鏈結以形成一個雙向鏈結環形串列。而且將 B-累堆的指標重設，使其指向有最小鍵值的最小樹之根節點。」

「圖 9.15 的最小樹分別為 $B_1, B_2, B_3$。你會發現 $B_k$ 恰好有 $2^k$ 個節點。再者，如果我們由空的 B-累堆之集合開始並且僅執行插入，結合，與刪除最小元素運算，則在每一 B-累堆中的比最小樹均為二系樹。這個觀察使得我們可以証明，當只有執行插入，結合，與刪除最小元素運算時，我們可以分攤成本，使得每一插入和結合的分攤成本 $O(1)$，每一刪除最小元素的分攤成本為 $O(\log n)$。」

令 $a$ 為有 $n$ 個元素的 B-累堆，它由開始為空的 B-累堆，僅執行一連串的插入，結合，和刪除最小元素所形成。在 $a$ 中的每一最小樹的分支度 $\le \log_2 n$。結果 $\texttt{MAX\_DEGREE} \le \lfloor \log_2 n \rfloor$，且每一刪除最小元素的實際成本為 $O(\log n + s)$。

證明：「因 $a$ 的每一最小樹為二系樹，其節點最多為 $n$，所以沒有一個最小樹的分支度可以大於 $\lfloor\log_2 n\rfloor$。□」

如果在開始為空的 B-累堆上執行一連串 $n$ 個插入，結合，刪除最小元素運算，則我們可以分攤成本，使得每一插入和結合的分攤時間複雜度為 $O(1)$，每一刪除最小元素的分攤時間複雜度為 $O(\log n)$。

證明的骨架：「對每一 B-累堆，根據下列方法，定義 #insert 和 last_size 兩個數值。」—— 用這兩個量當位能函數（potential function），證明每次刪除所做的額外工作，都已經預先由之前的插入付過了。

「費氏累堆（Fibonacci heap）是一種資料結構，它支援三種二系累堆的運算：插入，刪除最小或最大元素和結合，以及下列的運算：」

1. 刪除，刪除指定的節點中之元素。
2. 減少鍵值，將指定的節點之鍵值減去一個給定的正值。

「第一個運算可以在 $O(1)$ 分攤時間內完成，第二個運算可在 $O(\log n)$ 分攤時間完成。使用費氏累堆時，二系累堆的運算可以如同使用二系累堆時，以相同的漸近時間完成。」

要從 F-累堆 $a$ 刪除任一節點 $b$，以下列方式完成：

1. $a = b$，則執行一個刪除最小元素；否則執行下列步驟 2、3 和 4。
2. 從所屬的雙向鏈結串列中刪除 $b$。
3. 結合 $b$ 的子節點雙向鏈結串列和 $a$ 的最小樹根節的雙向鏈結串列，形成一個雙向鏈結串列。有相同分支度的樹並未如同刪除最小元素一般結合在一起。
4. 廢棄節點 $b$。

「除非要刪除最小的元素，任一刪除運算的實際成本為 $O(1)$。在此情況下，刪除運算的時間等於刪除最小元素運算的時間。」

減少某節點的鍵值後，它可能小於父節點，破壞最小樹性質。作法是把它從父節點切離，成為 F-累堆的一棵獨立最小樹。但若不加限制地切，樹會變得又瘦又長，破壞分支度的界限。

解法就是 child_cut：每個節點記錄「自從它成為現在這個父節點的子節點以來，是否已經失去過一個子節點」。當一個節點失去第二個子節點時，它自己也要被切離 —— 這個連鎖反應就是階段切割。

如果一連串的 $n$ 個插入、結合、刪除最小元素，刪除和減少鍵值運算在一開始為空的 F-累堆上執行，則可以分攤成本，使得每一個插入、結合、刪除運算的分攤成本為 $O(\log n)$。整個順序的全部時間複雜度為順序中各別運算的分攤複雜度之加總。

證明要點（課本原文）：「此定理之証明如同定理 9.1。#insert 之定義未改變。但 last_size 要改變。因為在每一刪除和刪除最小元素之後，last_size 則以 F-累堆中最小樹之個數為因數而改變（在圖 9.22 的範例中，last_size 增加了 5）。根據這個修改，可發現在刪除最小元素時，$s = \texttt{\#insert} \times \texttt{last\_size} + u - 1$。」

「因全部的階段分割次數受限於全部的刪除和減少鍵值運算的次數（因它們是能夠設定 child_cut 為 TRUE 僅有的運算），這種分割的成本可以分攤在刪除和減少鍵值運算上，每一運算的分攤成本加 1。刪除一個不是最小元素的分攤成本變成 $O(\log n)$，其實際成本為 $O(1)$……減少鍵值運算的分攤成本為 $O(1)$，其實際成本為 $O(1)$。」

精選參考文獻中寫明：「B-累堆和 F-累堆由 M. Fredman 和 R. Tarjan 提出。它們的工作發表在 "Fibonacci heaps and their uses in improved network optimization algorithms", JACM, 34, 3, July 1987, pp. 96–615。這篇論文也討論本章所提到的多種基本 F-累堆的改良，以及 F-累堆在指派問題（assignment problem），和找尋最小成生成樹的問題上之應用。」

關鍵就在「減少鍵值」這個運算：Prim 和 Dijkstra 的內層迴圈做的正是「更新某個頂點的距離估計」，而那在 F-累堆上是分攤 $O(1)$。對稀疏圖（$e \ll n^2$），這是實質的改進。

^† 常數因子比最小-最大累堆小。  ^‡ 最小版不支援；需要最大版（max-leftist tree / max-binomial heap）。

1. 最小-最大累堆：階層交錯（min/max/min/max…），delete_min 每次下沉兩層，要比較子節點與孫子節點。
2. Deap：根節點空著、左子樹最小累堆、右子樹最大累堆、左邊每個節點 $\le$ 右邊的鏡像節點。$n=1$ 代表空。
3. 左傾樹：$\textit{shortest}(x) \le \log_2(n+1)$（公設 9.1a），最右邊的路徑就是最短路徑（9.1b）。min_union 只往右遞迴，最後修復左傾性質。
4. 插入與刪除都可以用「結合」實作 —— 只要寫對 min_union 一個函數。
5. 成本分攤：分攤成本之加總 $\ge$ 實際成本之加總。用它得到更緊的上限 $\min\{2i+6d,\ i+10d\}$。
6. B-累堆：$B_k$ 恰好有 $2^k$ 個節點；樹集合 $\leftrightarrow$ $n$ 的二進位表示；合併相同分支度 = 二進位進位。
7. F-累堆：多了 parent 和 child_cut 兩個欄位。階段切割是正確性的必要條件（習題 3），它保證 $N_i = F_{i+2} \ge \Phi^i$。
8. F-累堆的回報：Prim 與 Dijkstra 從 $O(n^2)$ 改進到 $O(e+n\log n)$。