斐波那契堆(Fibonacci heap)是計(jì)算機(jī)科學(xué)中最小堆有序樹的集合。它和二項(xiàng)式堆有類似的性質(zhì)，可用于實(shí)現(xiàn)合并優(yōu)先隊(duì)列。

相關(guān)介紹

斐波那契堆的特點(diǎn)：不涉及刪除元素的操作有O(1)的平攤時(shí)間。 Extract-Min和Delete的數(shù)目和其它相比較小時(shí)效率更佳。

用途：稠密圖每次Decrease－key只要O(1)的平攤時(shí)間，和二項(xiàng)堆的O(lgn)相比是巨大的改進(jìn)。

斐波那契堆的結(jié)構(gòu)較二項(xiàng)堆更松散。因此對(duì)結(jié)構(gòu)的維護(hù)可以到方便時(shí)再做。

斐波那契堆中的樹是有根而無序的。每個(gè)節(jié)點(diǎn)包含一個(gè)指向其父節(jié)點(diǎn)的指針p[x]，以及一個(gè)指向其任一子女的指針child[x]（指向子女雙鏈表）。

每個(gè)孩子有l(wèi)eft[x]和right[x]。（意義：在O(1)的時(shí)間內(nèi)去掉一個(gè)節(jié)點(diǎn)，或者在O(1)的時(shí)間內(nèi)合并雙鏈表。）其它域： degree[x]存儲(chǔ)子女個(gè)數(shù)。 mark[x]指示自從x上一次成為另一節(jié)點(diǎn)的子女以來，它是否失掉一個(gè)孩子。

一個(gè)給定的斐波那契堆可以通過一個(gè)指向其含有最小關(guān)鍵字樹的指針來訪問。

斐波那契堆的關(guān)鍵思想在于盡量延遲對(duì)堆的維護(hù)。創(chuàng)建一個(gè)新的斐波那契堆： MAKE_Fib_Heap有O(1)的代價(jià)。

插入一個(gè)節(jié)點(diǎn)：分三步進(jìn)行： 1。為新的節(jié)點(diǎn)置p，child，left，right，mark等域。 O(1) 2。將包含x的根表和根表H連接。O(1) 3。在O(1)的時(shí)間內(nèi)調(diào)整指向該堆的指針min[x] O(1) 以節(jié)點(diǎn)數(shù)表示勢(shì)。勢(shì)的增加為1，實(shí)際代價(jià)為O(1)。所以平攤代價(jià)為O(1)。

尋找最小節(jié)點(diǎn)： min[x]指向的節(jié)點(diǎn)即為最小節(jié)點(diǎn)。因?yàn)閯?shì)沒有變化，所以這個(gè)操作的平攤代價(jià)為O(1)。

合并兩個(gè)斐波那契堆：分為3步： 1。合并根表 2。設(shè)置新的min[h] 3。重置n[x]。

抽取最小節(jié)點(diǎn)：這是最復(fù)雜的工作。被延遲的對(duì)根表的調(diào)整工作最終由這個(gè)操作進(jìn)行。 1。去掉最小值，將其每個(gè)孩子都加入根表。 2。將相同度數(shù)樹的合并。

調(diào)整根表的步驟 1。在根表中找出兩個(gè)具有相同度數(shù)的根x和y，且key[x]《key[y] 2。將y與x連接。將y從根表里去掉，成為x一個(gè)孩子，并增加degree[x]。

減小一個(gè)節(jié)點(diǎn)的權(quán) 1。若此減小不影響堆序，不作調(diào)整。 2。若影響堆序，則從堆中刪除該節(jié)點(diǎn)，將其加入根表。并檢查其父親的mark位。

若為false，則停止，并將其置為true。若為true，則刪除其父親，繼續(xù)遞歸向上執(zhí)行。直到一個(gè)

節(jié)點(diǎn)mark域?yàn)閒alse或該節(jié)點(diǎn)為根節(jié)點(diǎn)為止。

刪除一個(gè)節(jié)點(diǎn)： 1。將該節(jié)點(diǎn)權(quán)調(diào)整至最小 2。抽取最小值。

證明最大度數(shù)界：證明刪除或extract－min的平攤時(shí)間為O（lgn)。引理1：設(shè)x為斐波那契堆中任一節(jié)點(diǎn)，并假設(shè)degree[x]=k。設(shè)y1，y2，。。。yk表示按與x鏈接的次序排列的x的子女，從最早的到最遲的，則對(duì)i=2,3,...,k，有degree[y1]>=0且degree[yi]>=i-2 證明：顯然degree[y1]》=0 對(duì)i>=2，注意到y(tǒng)1被鏈接到x上時(shí)，y1，y2，。。yi－1都是x的子女，故我們必有degree[x]>=i-1 又僅當(dāng)degree[x]=degree[yi]時(shí)，才將yi鏈接到x上。故此時(shí)必有degree[yi>=i-1，在此之后，節(jié)點(diǎn)yi至多失去一個(gè)孩子，因?yàn)槭蓚€(gè)就被切斷了。所以degree[yi]>=i-2

引理2：對(duì)所有的整數(shù)k>=0，F(xiàn)k+2=1+sum（Fi） [0<=i<=k] ，F(xiàn)為斐波那契數(shù)。用數(shù)學(xué)歸納法證明。并可證明不等式 Fk+2 >= G^k ，其中G為黃金分割率。 (1+5^0.5)/2=1.161803...

引理3：設(shè)x為斐波那契堆中任一節(jié)點(diǎn)，并設(shè)k=degree[x]，那么，size(x)>=Fk+2>=G^k。

推論：在一個(gè)包含n個(gè)節(jié)點(diǎn)的斐波那契堆中節(jié)點(diǎn)的最大度數(shù)為O(lgn)。