# 一、綜述 ### 1.斐波那契堆 斐波那契堆是可合并堆 在不涉及刪除的操作（除去EXTRACT和DELETE）中，操作僅需O(1)的平攤運行時間 當EXTRACT和DELETE的操作數目較小時斐波那契堆能得到較好的運行效率。 斐波那契堆不能有效地支持SEARCH操作 用于解決諸如最小生成樹和尋找單源最短路徑等問題的快速算法都要用到斐波那契堆。 ### 2.斐波那契堆的結構 斐波那契堆由一組最小堆構成，這些最小堆是有根的無序樹。 結點結構： key: 關鍵字，作為排序、判斷結點大小的標準 left, right：用于維護雙鏈表，所有的根結點形成一個雙鏈表，每個結點的孩子們形成雙鏈表 parent, child : 維護父子關系 mark : 這個域與維護堆結構無關，只與具體的算法策略有關，不在這里講 degree： 記錄該結點有幾個孩子 斐波那契堆 n：堆中結點的個數 min：批向最小的結點 ### 3.可合并堆 引理19.1中給出的二項樹的性質對無序二項樹仍然成立P278 有n個結點FibHeap，結點的最大度數D(n) = lgn(向下取整) 將合并堆的操作盡可能地推后 ### 4.最大度數的界 在一個包含n個結點的斐波那契堆中，結點的最大度數D(n)為O(lgn) # 二、理解 ### 1.延遲合并操作 FIB-HEAP-INSERT和FIB-HEAP-UNION只是最基礎的鏈表合入操作，因為合并操作要盡可能地拖后 FIB-HEAP-EXTRACT-MIN除了要完成本職工作外，還要作合并調整 ### 2.合并調整操作 CONSOLIDATE是作合并調整的函數 它將度數相同的根鏈接起來，直到對應每個度數至多只有一個根 遍歷每一個根結點去判斷，如果兩個根結點的度是一樣的，讓大的結點作為小的結點的孩子 ### 3.mark的作用 為了防止堆太寬，需要策略來調整堆，使根結點成為別的根結點的孩子，該策略就是CONSOLIDATE 同理，為了防止堆太深，也需要有相應的策略去調整，在適當的時候，把某個結點的孩子變成根 這一策略就是CUT和CASCADING-CUT，mark在實現這一策略的過程中起到輔助作用。 原理：當一個非根結點被切掉了2個孩子，就把它升為根結點 在刪除一個結點時，怎么區分是第一個被刪除的孩子，還是第二個？此時需要用mark來標記 ### 4.P300那句話 因為翻譯不好，嚴重影響理解 一旦第二個孩子也失掉后，x與其父結點之間的聯系就被切斷了，并成為一個新根。 原文：As soon as the second child has been lost, we cut x from its parent, making it a new root. # 三、改進 ### 1.命名 mark的命名不能體現它的作用，影響理解，如果換一個好一點的名字，就不用那么大段的文字去說明 外部函數不需要FIB-HEAP-這樣的前綴，因為本來就是為它寫的接口 內部函數的名字要說明函數的作用，因為內部函數是被自己調用的，不要給自己添麻煩 ### 2.分解函數 提取了一些對雙鏈表的常用操作 ### 3.合并函數 CUT和CASCADING-CUT合并成一個函數，因為它們其實是一個功能，就是根據策略把孩子結點升為根結點 ### 4.參數和返回值 CUT和CASCADING-CUT中的x和y是父子關系，而且重點是子，父是只為了方便處理，不需要作為參數傳進來，在函數里面重新獲取一個就可以了。多傳一個函數，就一個出錯源 對于帶參數的函數，增加一返回值。用于告知調用者是否成功，或什么原因導致失敗 ### 5.功能 FIB-HEAP-DECREASE-KEY和FIB-HEAP-DELETE這兩個函數作用不大。 因為它們的入參是node*。要想調用這兩個函數，就必須先獲取目標結點的指針。 可是沒有一個接口返回指向結點的指針，怎么找到我的目標結點的指針呢？ 調用者必須自己在創建結點后保持這個結點，這樣不合理 # 四、代碼 ### 1.[FibHeap.h](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter20/FibHeap.h) ### 2.[FibHeap.cpp](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter20/FibHeap.cpp) ### 3.[測試用例](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter20/FibHeapTest.cpp) # 五、習題 ### 20.1斐波那契堆 ### 20.2可合并堆 ### 20.2-1  ### 20.2-4 McGee和FibHeap的區別在于合并的時機。 Fibheap認為合并調整應該盡量地推遲，而McGee則在每次堆中結點有增加的時候就作合并調整。 個人認為，合并調整操作的意義是防止堆過寬而影響性能。但是從算法過程上看，根結點的個數多少不會影響INSERT和UNION的性能，因此沒有必要。 比較認可FibHeap的做法。 ### 20.3減小一個關鍵字與刪除一個結點 ### 20.3-1 根據P300的描述，只有非根結點才可能被打上標記，如果根結點有標記，一定是它是非根結點的時候打上標記，然后被移到根結點的位置。 把結點移至根結點是通過上面代碼中的函數addNodeToRootList和addListToRootList完成的，目標縮小至這兩個函數周圍 讓根結點成為有標記結點，須滿足以下兩個條件 （1）調用這兩個函數前，該結點是非根結點 （2）調用后沒有清標記 結論：x是pMinData的孩子，根據P300的步驟被打上標記后，執行extract()時又成為根結點 ### 20.4最大度的界 # 四、思考題 ### 20-1刪除的另一種實現 把FIB-HEAP-DELETE中的兩個函數展開，再和PISANO-DELETE對比，并附上x不是min[H]的假設，可以發現這兩個函數執行的操作基本上是一樣的，區別在于 （1）PISANO-DELETE中去掉了FIB-HEAP-DELETE中多余的判斷，不影響效率 （2）FIB-HEAP-DELETE在刪掉結點之后有合并調整的動作 a)add x's child list to the root list of H的時間不是O(1)，因為每個child都有一個pParent指針，必須依次修改每個child的指針 ### 20-2其它斐波那契堆的操作 a) （1）k < key[x]的情況，直接調用FIB-HEAP-DECREASE-KEY （2）k = key[x]的情況，不用處理 （3）k > key[x]的情況，交換它與它孩子的內容，但是指針保持不變，直到符合最小堆的情況，時間與堆的深度有關 b) 以我有限的智商，只能想到執行min(r, n[H])次EXTRACT