一個優(yōu)先隊列需要支持的操作有
- insert 插入元素 \(x\)。
- find-min 返回最小的元素。
- delete-min 刪除最小的元素。
- decrease-key 將一個元素 \(x\) 減小 \(k\)。\(k \geq 0\)。
常用于實現(xiàn)優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu)是堆。
需要注意的是，小根堆需要支持 decrease-key，大根堆需要支持 increase-key。對于一個堆來說兩種操作的難度并不一致。以下均考慮小根堆。
還有一個可能支持的操作
- meld 合并兩個堆。也叫做 union / merge。
定義 一個堆是一種基于樹的數(shù)據(jù)結(jié)構(gòu)，滿足堆性質(zhì)
- \(A\) 是 \(B\) 的父親，則 \(A\) 的鍵值比 \(B\) 的鍵值小。
一些常見的優(yōu)先隊列實現(xiàn)方法的復(fù)雜度表
| 操作 | 鏈表 | 二叉堆 | 二項堆 | 斐波那契堆? | Brodal queue |
|---|---|---|---|---|---|
| insert | \(O(1)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\) | \(O(1)\) |
| delete-min | \(O(n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) |
| decrease-key | \(O(n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\) | \(O(1)\) |
| meld | \(O(1)\) | \(O(n)\) | \(O(\log n)\) | \(O(1)\) | \(O(1)\) |
| find-min | \(O(n)\) | \(O(1)\) | \(O(1)\) | \(O(1)\) | \(O(1)\) |
delete 能歸約到 decrease-key + delete-min，并且一般不會比這倆優(yōu)，所以不單獨寫了。
? 表示均攤復(fù)雜度。
我們先不介紹這些堆，先來看我們有了這些黑盒后如何優(yōu)化一些算法。一般的堆對算法的優(yōu)化是廣為人知的，Brodal queue 的實現(xiàn)又過于復(fù)雜并且只是斐波那契堆的復(fù)雜度變嚴(yán)格，所以接下來的例子均為斐波那契堆的應(yīng)用。
一個著名的例子是對 Dijkstra 算法的優(yōu)化。如果我們用 decrease-key 處理最短路數(shù)組的更新，Dijkstra 會進行 \(n\) 次 delete-min，\(n\) 次 insert，\(m\) 次 decrease-key。使用斐波那契堆可以做到 \(O(m + n \log n)\)。
類似地，Prim 算法會進行 \(n\) 次 delete-min，\(n\) 次 insert，\(m\) 次 decrease-key，因此可以做到 \(O(m + n \log n)\)。但和 Dijkstra 不同的是，這不是最優(yōu)的算法。最小生成樹問題弱于排序問題。
優(yōu)化點在于最小生成樹的割性質(zhì)：對于任意的 \(S \subseteq V\)，\(S\) 和 \(V \setminus S\) 之間的邊中邊權(quán)最小的那條一定在任一最小生成樹之中。這代表著我們把點集劃分為若干個集合，每個集合作為一個新點，跨越兩個集合的邊連在新點上得到的新圖的最小生成樹也會在舊圖上成立。由此我們可以遞歸。Bor?vka 算法就是這么做的。
我們從一個點開始做 Prim，到堆的大小 \(= k\) 時停止，把涉及到的點與其連出的邊合并為一個新點，再在新圖中找一個沒有被訪問過的點繼續(xù)做 Prim（也需要考慮和新點之間的連邊，否則正確性無法保證），這樣最后每個新點的度數(shù)都 \(\geq k\)，因此至多有 \(\frac {2m}k\) 個集合。根據(jù)割性質(zhì)，現(xiàn)在舊圖上最小生成樹剩下的邊可以通過求新圖上的最小生成樹得到，因此可以遞歸這個過程。
考慮令 \(k = 2^{\frac {2m}n}\) 則每輪的復(fù)雜度 \(O(m + n \log k) = O(m)\)，并且
因此第 \(i\) 輪滿足 \(\log^{(i)} \frac{2m}{n'} \geq \frac {2m}n\)，需要的輪數(shù)與 \(\min_i\left\{\log^{(i)} n \leq \frac mn\right\} =: \beta(m, n)\) 同階，因此總復(fù)雜度為 \(O(m \beta(m, n))\)。當(dāng) \(m = O(n)\) 時，復(fù)雜度也可寫為 \(O(m \log^* n)\)。
這個算法仍然不是最優(yōu)的。
- [Karger, Klein, Tarjan '95] \(O(m)\) 的隨機算法。
- [Chazelle '00] \(O(m\alpha(m, n))\) 的確定性算法。
- [Pettie, Ramachandran '02] 證明了的最優(yōu)算法，但是復(fù)雜度確界沒有給出，僅知道其在 \(\Omega(m)\) 和 \(O(m \alpha(m, n))\) 中。
- [Dixon, Rauch, Tarjan '92] \(O(m)\) 驗證一棵樹是否是最小生成樹。
接下來我們來介紹二項堆和斐波那契堆。
二項樹 \(B_n\) 是遞歸定義的一種樹。\(B_0\) 是一個單點，\(B_n\) 把兩棵 \(B_{n-1}\) 的根節(jié)點相連，并把其中一棵的根節(jié)點認(rèn)作新的根節(jié)點。\(|B_n| = 2^n\)。定義 \(B_n\) 的 \(\mathrm{rank}\) 為 \(n\)。
一個二項堆包含若干棵二項樹，滿足每棵樹都滿足堆性質(zhì)，且它們的的 \(\mathrm{rank}\) 互不相同。
由于 \(|B_n| = 2^n\)，把二項堆的大小 \(m\) 寫成二進制，值為 \(1\) 的那些數(shù)位恰好對應(yīng)一棵二項樹。因此二項堆中樹的棵數(shù)為 \(O(\log m)\)。
meld 如果有兩個相同 \(\mathrm{rank}\) 的二項樹，那么可以將兩者合并，將鍵值小的作為新的根節(jié)點，得到一個 \(\mathrm{rank}+1\) 的仍然滿足堆性質(zhì)的二項樹。我們可以將兩個堆的大小 \(m_1, m_2\) 寫成二進制，列豎式做加法，相同數(shù)位的樹便也做加法，進位到下一位上。
每一次合并的復(fù)雜度是 \(O(1)\)，因此總復(fù)雜度為 \(O(\log m)\)。
insert 將原樹和一個僅包含 \(B_0\) 的樹做 meld。復(fù)雜度為 \(O(\log m)\)。
delete-min 在所有二項樹中找到根節(jié)點鍵值最小的，將其所有兒子和剩下的二項樹做 meld。復(fù)雜度為 \(O(\log m)\)。
find-min 每次 delete-min 的時候維護一下。復(fù)雜度為 \(O(1)\)。
decrease-key 向上冒泡。因為樹深等于其 \(\mathrm{rank}\)，復(fù)雜度為 \(O(\log m)\)。
斐波那契堆基于二項堆的思路。它的大致想法是，與其每次都嚴(yán)格維護二項樹樹形，不如把需要的點直接從樹上拆下來，直到 delete-min 的時候再重構(gòu)，用勢能分析得到均攤復(fù)雜度。
一個斐波那契堆 \(H\) 仍然包含若干棵樹，每一棵樹都是刪去了一些子樹的二項樹。那些被刪去了兒子的點稱為標(biāo)記點。
定義 \(\mathrm{rank}(x)\) 為 \(x\) 的兒子個數(shù)。\(\mathrm{rank}(H) = \max_{x \in H} \mathrm{rank}(x)\)。\(\mathrm{tree}(H)\) 為 \(H\) 擁有的樹的棵數(shù)，\(\mathrm{marks}(H)\) 為 \(H\) 的標(biāo)記點的個數(shù)。
insert 直接將一個 \(B_0\) 放入 \(H\)，\(\mathrm{tree}(H)\) 加一。
delete-min 將其所有兒子放入 \(H\) 中，并將 \(\mathrm{rank}\) 相同的兩棵樹同二項樹一樣合并，直到?jīng)]有 \(\mathrm{rank}\) 相同的兩棵樹。
decrease-key 如果操作后堆性質(zhì)仍然滿足，不做任何事。否則其鍵值小于父親的鍵值，此時直接將這棵子樹從樹上拆下來，并將其父親設(shè)為標(biāo)記點。如果其父親已經(jīng)為標(biāo)記點，則將這個單點也拆下來，刪去其標(biāo)記，并再次考慮它的父親，循環(huán)這個過程直到一個未被標(biāo)記的點或者根，我們總是不標(biāo)記根。
這么做的動機是，一棵深的樹必須也得是重的。如果刪去了太多兒子，可能會導(dǎo)致其結(jié)點數(shù)很少但是深度很深，從而拖累復(fù)雜度。所以我們雖然允許拆子樹，但只允許一個結(jié)點拆一次，否則這棵子樹就要送去重構(gòu)。在之后的分析中我們會看到滿足條件的最小的樹的節(jié)點個數(shù)呈斐波那契數(shù)列（直觀地，\(|B_n| = |B_{n-1}| + |B_{n-1}| \Rightarrow |B'_n| \geq |B'_{n-1}| + |B'_{n-1\color{red}{-1}}|\)），這也是其名字的由來。
meld 把所有樹放到一起就好了。
接下來進行復(fù)雜度分析和一些實現(xiàn)細節(jié)的描述。
先來考慮形式化上面說的那段話。令 \(F_n\) 表示 \(\mathrm{rank} = n\) 的最小的樹的大小，滿足性質(zhì)
- 若 \(y_1, \ldots, y_k\) 是結(jié)點 \(x\) 的兒子按照 \(\mathrm{rank}\) 從小到大排序后的序列，則 \(\mathrm{rank}(y_i) \geq \max(0, i - 2)\)。
這條性質(zhì)是一個序列可以對應(yīng)斐波那契堆中一棵樹在某個時候的形態(tài)的充要條件。因為我們總是合并 \(\mathrm{rank}\) 相同的樹，當(dāng) \(x\) 已有 \(y_1, \ldots, y_{i-1}\) 時，稱其為 \(x_i\)，合并了 \(y_i\) 則有 \(\mathrm{rank}(y_i) = \mathrm{rank}(x_i) \geq i - 1\)，由于 \(y_i\) 至多失去一個孩子，\(\mathrm{rank}(y_i) \geq i - 2\)。而按照這個過程我們也能構(gòu)建出一棵樹與對應(yīng)的拆子樹操作來。
則一個 \(B'_n\) 可以通過某個 \(B'_{n-1}\) 加入第 \(n\) 個兒子得到，即加入某個 \(B'_{n-2}\) 得到，因此有 \(F_n = F_{n-1} + F_{n-2}\)，\(F_0 = 1, F_1 = 2\)，因此其是斐波那契數(shù)列，滿足 \(F_n \geq \left(\frac{1 + \sqrt 5}2\right)^n\)，故樹深總是樹重的 \(\log\)。
接下來考慮勢能函數(shù)。有兩個操作需要均攤分析，一個是樹的個數(shù)，一個是標(biāo)記的個數(shù)，前者在 delete-min 中用到，后者在 decrease-key 向上遞歸時用到。
令 \(\Phi(H) = \mathrm{tree}(H) + 2 \mathrm{marks}(H)\)，之所以要加倍數(shù) \(2\) 是因為將標(biāo)記點拆下來時 \(-\Delta\mathrm{marks}(H) = \Delta\mathrm{tree}(H)\)，但我們要統(tǒng)計這部分的實際開銷，如果不加倍數(shù)則勢能不變。因此勢能里兩者要相差一倍，加給誰都可以，但是既然 \(\mathrm{tree}(H)\) 要承擔(dān)更多的操作不如讓它是一倍的那位。
現(xiàn)在開始考慮每個操作的實際開銷與勢能變化。
insert 實際開銷 \(O(1)\)，勢能變化 \(+1\)，復(fù)雜度 \(O(1)\)。
delete-min 實際開銷 \(O(\mathrm{rank}(H)) + O(\mathrm{tree}(H))\)，勢能變化 \(\mathrm{tree}(H') - \mathrm{tree}(H) = O(\mathrm{rank}(H')) - \mathrm{tree}(H)\)，均攤復(fù)雜度 \(O(\mathrm{rank}(H)) + O(\mathrm{rank}(H')) = O(\log n)\)。
decrease-key 實際開銷 \(O(c)\)，\(c\) 為涉及的標(biāo)記點個數(shù)，勢能變化 \(\leq c + 2(-c + 2) = O(1) - c\)，均攤復(fù)雜度 \(O(1)\)。需要對兒子維護一個 \(O(1)\) 刪除、線性時間遍歷的數(shù)據(jù)結(jié)構(gòu)，一個簡單的實現(xiàn)是雙向循環(huán)鏈表。文章來源：http://www.zghlxwxcb.cn/news/detail-711661.html
meld 如果使用了雙向循環(huán)鏈表那 \(O(1)\) 的合并是簡單的。文章來源地址http://www.zghlxwxcb.cn/news/detail-711661.html
到了這里，關(guān)于[算法分析與設(shè)計] 2. 斐波那契堆及其應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
