二項堆和Fibonacci堆的分析與實現(xiàn)畢業(yè)設計論文

1、 本科生畢業(yè)設計（論文）題 目： 二項堆和fibonacci堆的分析與實現(xiàn) 姓 名： 陳 偉 學 號： 110901004 學 院： 數(shù)學與計算機科學學院 專 業(yè)： 計算機科學與技術 年 級： 2009 級 指導教師： （簽名） 年 月 日二項堆和fibonacci堆的分析與實現(xiàn)摘要堆是計算機科學中一類特殊的數(shù)據(jù)結構的統(tǒng)稱。堆通常被視為部分有序的樹形對象。 堆總是滿足堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值這個特殊性質。通常將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。常見的堆的實現(xiàn)包括二叉堆、二項堆，斐波那契堆。堆也是計算機程序設計中經常用到的數(shù)據(jù)結構，在最短路

2、算法的快速實現(xiàn)和最優(yōu)編碼的哈夫曼樹實現(xiàn)中都需要用到堆. 同時堆也經常作為優(yōu)先級隊列來使用，在程序調度算法中發(fā)揮重要作用。斐波那契堆有著非常好的均攤運行時間，可是其數(shù)據(jù)結構和算法實現(xiàn)相對比較復雜，因此人們一直在尋找一種既能實現(xiàn)較好的均攤運行時間，同時數(shù)據(jù)結構相對比較簡潔的實現(xiàn)算法。本課題的目的是學習連續(xù)空間上二叉堆的性質特點和離散空間上二項堆以及斐波那契堆的性質特點同時實現(xiàn)二項堆和斐波那契堆的具體算法。通過具體代碼實現(xiàn)來對比二項堆和斐波那契堆實現(xiàn)的時間空間上消耗，對比起各自的優(yōu)劣，同時探討堆在具體應用中發(fā)揮的作用。關鍵字：二叉堆，二項堆，斐波納契堆，實現(xiàn)算法。performance analys

3、is and implementation for binomial heap and fibonacci heapabstractheap is a special kind of data structure in computer science. heap is often viewed as partial ordered tree object. heap is always meet a special quality that the value of a node is always greater than or less than the value of its par

4、ent . usually the heap is called the maximum heap or big root heap if the value of root is the biggest, the minimum heap or small root heap if the value of root is the smallest. the implementation of heap including binary heap, binomial heap and fibonacci heap. heap is a kind of data structure which

5、 is often used in the design of computer program, it is used in the fast implementation of shortest path algorithm and optimal coding algorithm of huffman tree. simultaneously, heap is often used as a priority queue, playing an important role in process scheduling algorithm. fibonacci heap has a ver

6、y good capitation running time, but its data structure and algorithm implementation is relatively complicated, so people have been looking for a kind of data structure which has both good capitation running time and relatively simple implementation algorithm. the purpose of this subject is learning

7、the property of the binary heap on continuous space. at the same time, learning the property and specific implementation algorithm of binomial heap and fibonacci heap on discrete space. through specific code, we compare the time consumption and space consumption between binomial heap and fibonacci h

8、eap, and contrast their respective advantages and disadvantages. at the same time, we study the effect of heap in practical application.keywords: binary heap, binomial heap, fibonacci heap, implementation algorithm目錄第1章 緒論51.1 數(shù)據(jù)結構51.2 堆的定義和性質51.3 堆的類別61.4 本文主要內容6第2章 二叉堆72.1 二叉堆的定義72.2 二叉堆的存儲72.3 二叉

9、堆的基本操作72.4 二叉堆的應用局限性7第3章 二項堆83.1 二項樹83.2 二項堆93.3 二項堆的基本操作103.3.1 合并113.3.2 插入113.3.3 查找最小關鍵字123.3.4 刪除最小關鍵字123.3.5 減小關鍵字值123.3.6 刪除節(jié)點12第4章 斐波那契堆134.1 斐波納契堆的定義134.2 斐波納契堆的特點134.3 斐波那契堆操作144.3.1 創(chuàng)建144.3.2 插入154.3.3 刪除最小關鍵字154.3.4 減小關鍵字值164.3.5 刪除節(jié)點18第5章 實現(xiàn)細節(jié)185.1 二項堆代碼結構195.2 斐波納契堆代碼結構205.3 其他函數(shù)20第6章

10、性能分析20總結與展望22參考文獻23第1章 緒論在信息化時代，電子計算機在我們日常生活中扮演利益重要的作用。從電子郵件到網(wǎng)上視頻，從網(wǎng)絡游戲到三色定理證明，程序無處不在。隨著處理數(shù)據(jù)規(guī)模的日益增加，如何讓程序高效穩(wěn)定運行成為人們思考的問題。此時良好的數(shù)據(jù)結構和精心設計的算法便成為解決問題的重點。1.1數(shù)據(jù)結構數(shù)據(jù)結構是計算機科學中一個普遍而又重要的概念。數(shù)據(jù)結構是指計算機內部存儲和組織數(shù)據(jù)的方式。通常包括鏈式數(shù)據(jù)結構比如數(shù)組，單鏈表，雙鏈表，還有循環(huán)鏈表，樹式數(shù)據(jù)結構比如二叉樹，2-3樹等等。通過精心設計數(shù)據(jù)結構和建立在對應數(shù)據(jù)結構上的各種操作，通常情況下能夠使得程序運行的更加高效和穩(wěn)定。常

11、見的數(shù)據(jù)結構包括紅黑樹，avl樹，b樹，二叉堆，棧等等。在面對現(xiàn)實世界中的具體問題時，我們通過抽象來建立對應的數(shù)學描述，選擇合理的數(shù)據(jù)結構能夠對問題的高效解決起到事半功倍的作用。1.2 堆的定義堆是計算機科學中最常用的數(shù)據(jù)結構之一。從抽象的角度來講，堆是部分有序的樹形結構。它滿足任意節(jié)點的關鍵字值總是比起父節(jié)點的關鍵字值來的?。ㄗ钚《眩┗蛘呷我夤?jié)點的關鍵字值總是比起父節(jié)點的關鍵來的大（最大堆）。在本文的正文部份，如果沒有特殊說明，我們總是假定在討論最小堆。它高效支持插入，彈出，刪除和改變關鍵字值的操作。由于這些特殊性質，使得它在許多具體算法中得到普遍應用，例如最短路算法的快速實現(xiàn)，最優(yōu)編碼的哈

12、夫曼樹實現(xiàn)，優(yōu)先級調度算法等等。1.3 堆的分類從物理的角度來講，堆的節(jié)點在內存中可以連續(xù)分布也可以分散分布，前者是二叉堆，后者是二項堆和斐波納契堆。二叉堆的實現(xiàn)相對簡單，運行時間的常數(shù)因子也小，但是同時也存在一些不足之處。由于二叉堆要求連續(xù)的存儲空間，因此對于增量數(shù)據(jù)即我們無法事先預知數(shù)據(jù)總的規(guī)模的情況下，我們無法確定應該分配的內存大小。通常這種情況下我們傾向于分配一個較大的內存，但是極有可能造成內存的浪費，同時當數(shù)據(jù)規(guī)模超過分配的內存時還要重新分配內存，其中就要涉及較大的數(shù)據(jù)復制操作，這對運行效率是極其不利的。另外一種情況下及時我們事先知道數(shù)據(jù)規(guī)模的大小，但是由于內存有限無法分配出足夠大連

13、續(xù)的內存空間。由于這兩個原因使得二叉堆的應用得到限制，許多人開始探索離散空間上實現(xiàn)堆的方法。二項堆和斐波納契堆是離散空間上堆的實現(xiàn)，克服了二叉堆要求分配連續(xù)內存的缺點同時維持了相關操作的高效性。在漸近時間復雜度上二項堆和二叉堆的時間復雜度是相同的。斐波納契堆由于采用了循環(huán)雙向鏈表的數(shù)據(jù)結構使得在不涉及刪除操作的情況下時間復雜度為o(1)，從而大大提高時間效率。不過由于數(shù)據(jù)結構相對復雜，斐波那契堆的常數(shù)因子較大，在較小規(guī)模的數(shù)據(jù)上的時間優(yōu)勢并不明顯。本文通過學習兩種數(shù)據(jù)結構的數(shù)學性質和實現(xiàn)算法給出具體的代碼實現(xiàn)，同時比較了兩種數(shù)據(jù)結構的時間效率。1.4 本文主要內容本文結構內容安排如下：第一章

14、介紹數(shù)據(jù)結構的重要性同時引出堆這一重要數(shù)據(jù)結構。同時給出堆的一下基本認識。同時在本章中給出本文的結構安排。第二章 介紹二叉堆的結構，數(shù)學性質和具體的操作。第三章 介紹二項堆的結構，數(shù)學額性質和基本操作的相關算法。對二項堆的效率分析有個比較清楚的認識。第四章 介紹斐波納契堆的數(shù)據(jù)結構和基本操作的算法實現(xiàn)。第五章 介紹具體的代碼實現(xiàn)和性能分析。第六章 總結與展望第2章 二叉堆2.1 二叉堆定義二叉堆是一種應用廣泛的堆結構。二叉堆是完全二叉樹或者是近似完全二叉樹。二叉堆滿足堆特性：父節(jié)點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值，且每個節(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小

15、堆）。當父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。 當父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。2.2 二叉堆存儲二叉堆在內存中連續(xù)存儲使用數(shù)組表示。例如，假設根節(jié)點在數(shù)組中的位置是1，則第n個位置的左右子節(jié)點分別在2n和 2n+1的位置，其父節(jié)點處于n/2的位置。因此，第1個位置的左右子節(jié)點分別在2和3，第2個位置的左右子節(jié)點分別在4和5，以此類推。二叉堆的連續(xù)存儲性質使得我們能夠在o(1)時間內迅速定位父節(jié)點和子節(jié)點的位置。 上圖反應了二叉堆的邏輯結構和在內存中的物理結構。2.3二叉樹基本操作二叉堆可以在時間內進行插入節(jié)點，刪除節(jié)，改變節(jié)點的值等基本操作，同

16、時能夠在o(1)時間內獲得最小值。第3章 二項堆3.1二項樹定義二項樹是一種通過遞歸定義的有序樹，可以由以下定義得到： (1) 度數(shù)為0的二項樹只包含一個結點。(2) 度數(shù)為k的二項樹由兩棵度數(shù)為k-1的二叉樹構成，其中的一棵二叉樹的根節(jié)點成為另一棵二叉樹的最左孩子節(jié)點。上圖(a)反應了怎樣由兩棵度數(shù)為k-1的二叉樹構造度數(shù)為k的二叉樹。上圖(b)中的二叉樹從左至右度數(shù)分別為0至4。.上圖(c)反應了對于度數(shù)為k的二叉樹其直接的對應的二叉樹的度數(shù)從左到右依次是k-1,k-20。因此我們得出度數(shù)為k的二項樹共有個結點，高度為k，在深度d處有個結點。3.2二項堆定義二項堆是指滿足以下性質的二項樹的

17、集合：(1)每棵二項樹都滿足堆性質，即任意結點關鍵字大于等于其父結點的關鍵字。(2)集合中不能有兩棵或者兩棵以上的二項樹有相同度數(shù)。上圖是含13個結點的二項堆示意圖。由于我們并不需要對二項樹的根結點進行隨機存取的操作，我們將這些根節(jié)點按照度數(shù)從小到大的次序鏈接成一條單鏈，形成的鏈表我們稱為主鏈。因此以上第一個性質保證了二項樹的主鏈包含了最小的關鍵字。以上第二個性質則說明結點數(shù)為n的二項堆的根鏈上至多有棵二項樹。對于二叉堆中的每個節(jié)點x包括以下屬性：子女個數(shù)x.degree，最左孩子x.lchild，右兄弟x.rsibling，父節(jié)點x.par， 關鍵字x.key。對于一個抽象的二項堆h，h.h

18、ead表示主鏈首部，h.size表示堆中節(jié)點的個數(shù)。3.3二項堆的操作3.3.1 合并上圖是兩棵二項樹合并的示意圖。上圖是兩個二叉堆合并的示意圖。最基本的為二個度數(shù)相同的二項樹的合并。由于二項樹根結點包含最小的關鍵字，因此在二顆樹合并時，只需比較二個根結點關鍵字的大小，其中含小關鍵字的結點成為結果樹的根結點，另一棵樹則變成結果樹的最左孩子。偽代碼如下：bin_link(y, z)1 y.par z2 y.rsibling z.lchild3 z.lchild y4 z.degree z.degree+1上圖是如何遍歷主鏈的示意圖。兩個二項堆的合并可按如下步驟進行：因為主鏈上的根節(jié)點的度數(shù)i從小

19、到大排列且不存在兩個相同度數(shù)的根節(jié)點在同一主鏈上，因此可以對兩個主鏈按照根節(jié)點的度數(shù)從小到大進行遍歷合并得到一條主鏈。在得到的這條主鏈上度數(shù)為i的根節(jié)點至多有兩個且相鄰。因此我們對主鏈進行一次遍歷，在遍歷過程中度數(shù)為i的根節(jié)點只可能有1個，2個或者3個。我們利用三個指針prev_x，x，next_x來遍歷主鏈。來如果當前度數(shù)為i的根結只有一個或者三個則指針指向下一個節(jié)點，如果只有兩個則合并兩棵二叉樹并且將新的根節(jié)點加入主鏈。由于含有n個節(jié)點的二叉堆的主鏈長度不超過logn+1，并且我們只遍歷了兩遍主鏈，因此合并操作的時間復雜度為。偽代碼如下:bin_union(h)1 h = bin_make

20、()2 h.head = bin_merge(h1,h2)3 free objects h1 and h2 but not the lists they point to4 if h.head = nil5 return h6 prev_x = nil7 x = h.head8 next_x = x.rsibling9 while next_x != nil10if (x.degree != next_x.degree) or (next_x.rsibling != nil and next_x.rsibling.degree = x.degree)11prev_x = x, x = next

21、12else if x.key = next_x.key13x.rsibling = next_x.rsibling14bin_link(next_x, x)15else if prev_x = nil16h.head = next_x17else18prev_x.rsibling = next_x19bin_link(x, next_x)20x = next_x21next_x = x.rsibling22 return h3.3.2 插入創(chuàng)建一個只包含要插入關鍵字的堆，再將此堆與原先的二項堆進行合并，即可得到插入后的堆。由于需要合并操作的時間復雜度為，因此插入操作的時間復雜度為。偽代碼如下

22、：bin_insert(h，x)1 subh = bin_make()2 x.par = x.lchild = x.rsibling = x.degree = subh.head = nil3 h = bin_union(h, subh)3.3.3 查找最小關鍵字由于滿足最小堆性質，只需對二項堆的主鏈進行一遍遍歷即可，因為n個節(jié)點的二項堆的主鏈長度不超過logn+1，所以查找最小關鍵字操作的時間復雜度為。偽代碼如下：bin_top (h)1 y = nil2 x = h.head3 min = infinite4 while x != nil5if x.key min6min = x.key7

23、y = x8x = x.rsibling9 return y3.3.4 刪除最小關鍵字首先先找到最小關鍵字所在結點，將該節(jié)點的子樹看作一個獨立的二項堆，再將此堆合并到原先的堆中，然后刪除最小關鍵節(jié)點即可。由于每棵樹最多有l(wèi)ogn+1棵子樹，創(chuàng)建新堆的時間為。同時合并堆的時間也為，故整個操作的時間復雜度為。偽代碼如下：bin_pop(h)1 find the node with smallest key value on main chain and remove it from main chain.2 subh = bin_make()3 reverse the order of the l

24、inked list of xs children, set the p field of each child to nil and set headh to the the head of the resulting list.4 h = bin_union(h, subh)5 return x3.3.5 減小關鍵字的值由于在減小關鍵字的值后，可能不再滿足最小堆性質。此時，將其所在結點與父結點交換關鍵字同時將指針指向父節(jié)點。重復上述操作直到該節(jié)點為根節(jié)點或者該節(jié)點的關鍵值小于其父節(jié)點的關鍵字及最小堆性質得到滿足。操作的時間復雜度為。偽代碼如下：bin_decrease(h，x, k)1 x

25、.key = k ,y = x, z = x.par2 while z !=nil and y.key z.key3swamp x.key and y.key4y = z, z = x.par3.3.6 刪除將需要刪除的結點的關鍵字的值減小到負無窮大（比二項堆中的其他所有關鍵字的值都小即可），再刪除最小關鍵字的結點即可。偽代碼如下：bin_delete(h, x)1 bin_decrease(h, x, -infinite)2 bin_pop(h)第4章 斐波那契堆4.1斐波納契堆定義斐波那契堆是計算計科學中中最小堆有序樹的集合，它和二項堆有類似的性質。斐波那契堆不涉及刪除元素的操作有o(1)

26、的平攤時間，因此如果程序中decrease和delete操作較少則能夠獲得極高效率。斐波那契堆中每個節(jié)點x包含指向父節(jié)點的指針x.par，指向任意一個子結點的x.child，表示x的節(jié)點個數(shù)x.degree，指向它的左兄弟的y.left和右兄弟的y.right。同時x的所有子節(jié)點都用雙向循環(huán)鏈表鏈接起來。4.2 斐波納契堆的特點與二項堆相似,斐波那契堆也是一種可合并堆，是由一組堆有序樹decrease和構成的集合。如果不對斐波納契堆進行decrease和delete操作那么集合中的樹都是二叉樹?？墒侨绻嬖赿ecrease和delete操作時必然會破壞二項圖的結構。在這種情況下會出現(xiàn)樹高為k，

27、結點個數(shù)少于2k的情況。與二項堆不同的是主鏈上的堆有序樹不必按照度數(shù)大小從小到大排列。 上圖是斐波那契堆的示意圖。斐波那契堆中每個節(jié)點的屬性包括：父節(jié)點x.par，指向任一子女的指針x.child，左兄弟x.left，右兄弟x.right，子女的個數(shù)x.degree，布爾值域x.mark。其中任意節(jié)點的所有子女被組織成循環(huán)雙向鏈表，x.mark表示節(jié)點x成為另一個節(jié)點的子節(jié)點以來是否失去了一個孩子。對于一個特定的斐波那契堆，我們構造一個數(shù)據(jù)結構h，其中h.size表示堆的大小，h.min指向堆中最小節(jié)點。在斐波那契堆中，所有樹的根節(jié)點都鏈接成一個環(huán)形的雙鏈表，稱為堆的根表。 4.3 斐波納契堆

28、操作 斐波那契堆支持所有的堆操作，對于不涉及delete的操作有o(1)的均攤運行時間，其關鍵思想是將主鏈上的根節(jié)點的合并操作盡可能退后，來達到提高時間效率的目的。4.3.1 創(chuàng)建一個新的斐波那契堆過程fib_make() 分配并初始化一個斐波那契堆對象h。4.3.2 插入一個結點 首先分配并且初始化一個節(jié)點x然后加入h的根表中。偽代碼如下：fib_insert(h, x)1 x.degree = 0, x.par = nil, x.child = nil, x.left = x, x.right = x, x.mark =false2 merge the root list which co

29、ntains x to root list h3 if h.min = =nil or x.key h.min.key4 h.min = x5 h.n = h.n + 1 下圖將關鍵字為21的結點插入斐波那契堆的示意圖。4.3.3 合并兩個斐波那契堆由于雙向鏈表的數(shù)據(jù)結構同時根表上的節(jié)點度數(shù)無序的性質，因此只需把兩個根表連接同時比較最小關鍵節(jié)點取其中較小的即可。偽代碼如下：fib_union(h1, h2)1 h = fib_make()2 h.min = h1.min3 merge the root list of h2 with the root list of h4 if (h1.min

30、 = nil) or (h2.min != nil and h2.min y.key9exchange x y10 fib_link(h, y, x)11 ad = nil12 d = d + 113 ad = x14 h.min = nil15 for i = 0 to d(h.n)16 do if ai nil17 add ai to the root list of h18 if h.min = nil or ai.key x.key2error new key is greater than current key3 x.key = k4 y = x.par5 if y != nil

31、and x.key y.key6cut(h, x, y)7 cascading-cut(h, y)8 if x.key h.min.key9 h.min = xcut(h, x, y)1 remove x from the child list of y, decrementing degreey2 add x to the root list of h3 x.par = nil4 x.mark = falsecascading-cut(h, y)1 z = y.par2 if z != nil3 if y.mark = false4 y.mark =true5 else cut(h, y,

32、z)6 cascading-cut(h, z)下圖中：(a),(b)46減小為5； (c),(d),(e)35減小為5級聯(lián)剪切的過程如下：當節(jié)點y被加入根鏈后同時檢查指針y.par指向的節(jié)點，如果y.par.mark = = true那么對y.par進行級聯(lián)剪切的操作，否則另y.par.mark = true，操作結束。那么為什么偶數(shù)個的時候要遞歸往上刪除？因為度數(shù)為k的二項樹在i層共有c(k, i)個結點(i= 0, 1, 2, , k)。如果不進行級聯(lián)剪枝操作的話，我們可以發(fā)現(xiàn)刪除幾個節(jié)點后樹的形狀就會顯得十分凌亂毫無章法。但是如果進行了級聯(lián)剪枝，在偶數(shù)個結點時進行級聯(lián)剪切時，原來是c(3

33、, 0 )= 1, c(3, 1) = 3, c(3, 2) = 3, c(3, 3) = 1, 減少兩個結點關鍵字后，變?yōu)椋篶(2, 0) = 0，c(2, 1) = 2， c(2, 2) = 1;由于二項式是對稱的，因此通過級聯(lián)減枝的技術可以保證類使二項式減少一個數(shù)量級，維持二項樹的形狀。4.3.6 刪除一個結點刪除操作的過程比較簡單，首先減小對應節(jié)點的關鍵字值直到h.min所指向節(jié)點的關鍵字值小,此時對應節(jié)點成為h.min, 然后調用彈出操作函數(shù)即可。偽代碼如下：fib_delete(h, x)1 fib_decrease (h, x, -)2 fib_pop (h)第5章 實現(xiàn)細節(jié)5.

34、1二項堆代碼結構二項堆涉及到的數(shù)據(jù)結構主要包括bin_node 和 bin_heap，具體定義如下：struct bin_node struct bin_node *father;struct bin_node *lchild;struct bin_node *rsibling;void *data;int degree;struct bin_heap struct bin_node *head;int size;主要涉及到的函數(shù)如下：bin_make(),此函數(shù)分配一個bin_heap結構體指針并且初始化然后返回對應的結構體指針。bin_link(),此函數(shù)接受兩個bin_node結構體指針

35、作為參數(shù)，將對應的兩棵二項樹合并并且返回結果樹的根節(jié)點指針。bin_merge(),此函數(shù)接受兩個bin_heap結構體指針作為參數(shù)，將對應的兩個二項堆的主鏈按序合并，并將結果主鏈的頭部指針返回。bin_union(),此函數(shù)接受兩個bin_heap結構體指針作為參數(shù)，內部調用bin_merge()合并主鏈，然后對主鏈上相同度數(shù)的節(jié)點進行進一步合并。bin_replace(),此函數(shù)改變某個節(jié)點的關鍵字值，并且通過遞歸的父節(jié)點比較關鍵字值來維持堆的有序結構。bin_size(),此函數(shù)返回二項堆的節(jié)點數(shù)目。bin_empty(),此函數(shù)返回一個布爾值來判定對應的二項堆是否為空。bin_dele

36、te()，此函數(shù)刪除某個給定的節(jié)點，通過進一步的操作來保證二項堆的數(shù)學性質和結構。bin_push(),bin_pop(),bin_top(),這些函數(shù)對堆的基本操作進行封裝，提供抽象的接口。bin_func_test(),二項堆的測試函數(shù)，不包括效率測試，主要是對push,pop，top接口函數(shù)的測試。5.2斐波納契堆代碼結構斐波那契堆涉及到的數(shù)據(jù)結構主要包括fib_node 和 fib_heap，具體定義如下：struct fib_node struct fib_node *left;struct fib_node *right;struct fib_node *child;struct

37、fib_node *father;int mark;int degree;void *data;struct fib_heap struct fib_node *head;int size;主要涉及到的函數(shù)如下：fib_make(),此函數(shù)在內存中分配一個fib_heap的結構體并且初始化，函數(shù)返回對應結構體的指針。fib_link(),此函數(shù)接受兩個fib_node結構體指針，將兩個無序的二項樹合并，并且返回對應結果樹的根節(jié)點。fib_replace(),此函數(shù)改變某個節(jié)點的關鍵值，同時經過級聯(lián)剪切的操作的維護斐波那契堆的數(shù)學性質和結構。fib_union(),此函數(shù)接受兩個fib_heap結構體指針，將對應的斐波納契堆合并，返回合并后的堆的根節(jié)點。_listsize(),此函數(shù)接受一個fib_heap結構體指針，通過遍歷根鏈得到根鏈長度的最大度數(shù)，通