斐波那契堆

斐波那契堆(Fibonacci heap)是計算機科學中最小堆有序樹的集合。它和二項式堆有類似的性質，可用於實現合併優先佇列。

斐波那契堆的特點：不涉及刪除元素的操作有O(1)的平攤時間。 Extract-Min和Delete的數目和其它相比較小時效率更佳。
用途：稠密圖每次Decrease－key只要O(1)的平攤時間，和二項堆的O(lgn)相比是巨大的改進。
斐波那契堆的結構較二項堆更鬆散。因此對結構的維護可以到方便時再做。
斐波那契堆中的樹是有根而無序的。每個節點包含一個指向其父節點的指針p[x]，以及一個指向其任一子女的指針child[x]（指向子女雙鍊表）。
每個孩子有left[x]和right[x]。（意義：在O(1)的時間內去掉一個節點，或者在O(1)的時間內合併雙鍊表。）其它域： degree[x]存儲子女個數。 mark[x]指示自從x上一次成為另一節點的子女以來，它是否失掉一個孩子。
一個給定的斐波那契堆可以通過一個指向其含有最小關鍵字樹的指針來訪問。
斐波那契堆的關鍵思想在於儘量延遲對堆的維護。創建一個新的斐波那契堆： MAKE_Fib_Heap有O(1)的代價。
插入一個節點：分三步進行： 1。為新的節點置p，child，left，right，mark等域。 O(1) 2。將包含x的根表和根表H連線。O(1) 3。在O(1)的時間內調整指向該堆的指針min[x] O(1) 以節點數表示勢。勢的增加為1，實際代價為O(1)。所以平攤代價為O(1)。
尋找最小節點： min[x]指向的節點即為最小節點。因為勢沒有變化，所以這個操作的平攤代價為O(1)。
合併兩個斐波那契堆：分為3步： 1。合併根表 2。設定新的min[h] 3。重置n[x]。
抽取最小節點：這是最複雜的工作。被延遲的對根表的調整工作最終由這個操作進行。 1。去掉最小值，將其每個孩子都加入根表。 2。將相同度數樹的合併。
調整根表的步驟 1。在根表中找出兩個具有相同度數的根x和y，且key[x]《key[y] 2。將y與x連線。將y從根表里去掉，成為x一個孩子，並增加degree[x]。
減小一個節點的權 1。若此減小不影響堆序，不作調整。 2。若影響堆序，則從堆中刪除該節點，將其加入根表。並檢查其父親的mark位。
若為false，則停止，並將其置為true。若為true，則刪除其父親，繼續遞歸向上執行。直到一個
節點mark域為false或該節點為根節點為止。
刪除一個節點： 1。將該節點權調整至最小 2。抽取最小值。
證明最大度數界：證明刪除或extract－min的平攤時間為O（lgn)。引理1：設x為斐波那契堆中任一節點，並假設degree[x]=k。設y1，y2，。。。yk表示按與x連結的次序排列的x的子女，從最早的到最遲的，則對i=2,3,...,k，有degree[y1]>=0且degree[yi]>=i-2 證明：顯然degree[y1]》=0 對i>=2，注意到y1被連結到x上時，y1，y2，。。yi－1都是x的子女，故我們必有degree[x]>=i-1 又僅當degree[x]=degree[yi]時，才將yi連結到x上。故此時必有degree[yi>=i-1，在此之後，節點yi至多失去一個孩子，因為失去兩個就被切斷了。所以degree[yi]>=i-2
引理2：對所有的整數k>=0，Fk+2=1+sum（Fi） &#91;0<=i<=k&#93; ，F為斐波那契數。用數學歸納法證明。並可證明不等式 Fk+2 >= G^k ，其中G為黃金分割率。 (1+5^0.5)/2=1.161803...
引理3：設x為斐波那契堆中任一節點，並設k=degree&#91;x&#93;，那么，size(x)>=Fk+2>=G^k。
推論：在一個包含n個節點的斐波那契堆中節點的最大度數為O(lgn)。