【正文】 27 。 [4] 嚴蔚敏 吳偉民 《數(shù)據(jù)結構》 清華大學出版社 。 [2] Jon Bentley 《編程珠璣》第三版，人民郵電出版社。 最后，感謝各位評審老師在百忙之中抽出寶貴的時間對本論文進行審閱和參加答辯。在論文的編寫過程中，陳歡老師提出了許多的寶貴意見和建議，使我得到了很大的啟發(fā)。而這也是 我們要努力的目標。但是相對而言斐波納契堆有著復雜的數(shù)據(jù)結構和算法是其主要的不足。二項堆解決了離散空間上面堆的實現(xiàn)問題，與二叉堆有相同的漸近時間復雜度。人們不停的在探索這種抽象數(shù)據(jù)結構更好的實現(xiàn)算法。從計算機科學誕生伊始，數(shù)據(jù)結構和算法設計也隨之產(chǎn)生，一代一代的計算機科學家，工程師為了解決問題提出了許許多多的精巧的數(shù)據(jù)結構和算法設計。 面對日益增加的數(shù)據(jù)處理規(guī)模，常規(guī)的數(shù)據(jù)結構和算法無法滿足運行時間的要求。其中 clocks 代表 push操作耗費的掛鐘時間， clocks 代表 pop 操作耗費的掛鐘時間， sds 代表 push操作耗 費了幾秒， sds 代表 pop 操作耗費了幾秒， all 代表一次實驗總共耗費的時間。 通過 對 100000 個數(shù) 據(jù)進行測試 的實驗 ， 我們 得到下列結果 。它有 2 個參數(shù)，分別是 t 即實驗重復次數(shù)， mode 即表明是對二項堆還是對斐波那契堆進行測試，或者以比較模式進行測試。重復這樣的測試多次取 平均值。 福州大學本科生畢業(yè)設計 (論文 ) 22 第 6 章 性能測試 我們對二項堆和斐波那契堆的 Push 和 Pop 操作進行測試。重復這個這個操作多遍，取平均值。在代碼中為 raise()。在二項堆中為 repr()，在斐波那契堆中為 _repr()。在二項堆中為 le()，在斐波納契堆為 _le()。 fib_func_test（） ,斐波納契堆的測試函數(shù)，不包括性能測試，主要是對 Push,Pop和 Top 操作進行測試。 consolidate(),此函數(shù)實現(xiàn)級聯(lián)剪切的操作。 fib_Union(),此函數(shù)接受兩個 fib_heap 結構體指針，將對應的斐波納契堆合并，返回合并后的堆的根節(jié)點。 fib_link(),此函數(shù)接受兩個 fib_node 結構體指針，將兩個無序的二項樹合并，并且返回對應結果樹的根節(jié)點。 }。 struct fib_heap { struct fib_node *head。 void *data。 int mark。 struct fib_node *child。 福州大學本科生畢業(yè)設計 (論文 ) 20 斐波納契堆 代碼結構 斐波那契堆涉及到的數(shù)據(jù)結構主要包括 fib_node 和 fib_heap，具體定義如下： struct fib_node { struct fib_node *left。 bin_Push(),bin_Pop(),bin_Top(),這些函數(shù)對堆的基本操作進行封裝 ，提供抽象的接口。 bin_empty(),此函數(shù)返回一個布爾值來判定對應的二項堆是否為空。 bin_replace(),此函數(shù)改變某個節(jié)點的關鍵字值，并且通過遞歸的父節(jié)點比較關鍵字值來維持堆的有序結構。 bin_merge(),此函數(shù)接受兩個 bin_heap 結構體指針作為參數(shù)，將對應的兩個二項堆的主鏈按序合并，并將結果主鏈的頭部指針返回。 主要涉及到的函數(shù)如下： bin_Make(),此函數(shù)分配一個 bin_heap 結構體指針并且初始化然后返回對應的結構體指針。 int size。 }。 void *data。 struct bin_node *lchild。 福州大學本科生畢業(yè)設計 (論文 ) 18 刪除一個結點 刪除操作的 過程 比較 簡單， 首先 減小 對應節(jié)點的關鍵字值 直到 所指向節(jié)點的關鍵字值小 ,此時對應節(jié)點成為 , 然后 調(diào)用彈出操作函數(shù)即可。由于 二項式是對稱的， 因此通過級聯(lián)減枝的技術 可以保證類使二項式減少一個數(shù)量級 ，維持二項樹的形狀。如果不進行級聯(lián)剪枝 操作的話 ， 我們 可以發(fā)現(xiàn) 刪除幾個節(jié)點后樹的形狀就會顯得十分凌亂 毫無章法。 偽代碼如下： 1 if k 2 error new key is greater than current key 3 = k 4 y = 5 if y != NIL and 17 6 CUT(H, x, y) 7 CASCADINGCUT(H, y) 8 if 9 = x CUT(H, x, y) 1 remove x from the child list of y, decrementing degree[y] 2 add x to the root list of H 3 = NIL 4 = FALSE CASCADINGCUT(H, y) 1 z = 2 if z != NIL 3 if = FALSE 4 =TRUE 5 else CUT(H, y, z) 6 CASCADINGCUT(H, z) 下 圖中： (a),(b)46 減小為 5； (c),(d),(e)35 減小為 5 級聯(lián)剪切的過程如下：當節(jié)點 y 被加入根鏈后同時檢查指針 指向的節(jié)點，如果 = = true 那么對 進行級聯(lián)剪切的操作，否則另 == true，操作結束。 減小一個關鍵字 斐波那契堆利用 級聯(lián)剪枝 的技術來維護斐波那契的性質(zhì) 。 while 循環(huán)反復講相同度數(shù)的二叉樹進行連接操作 。 A[i]中存放著對應度數(shù)為 i 的二叉樹根節(jié)點。 Consolidate 過程要做的工作是 通過遍歷一遍根鏈使得有相同度數(shù)的根節(jié)點合福州大學本科生畢業(yè)設計 (論文 ) 16 并，最終使得根鏈上不存在度數(shù)相同的根節(jié)點。注意 這 里 并不是真正的最小結點 還需要調(diào)用Consolidatel 來確定最終 的值 。偽代碼 如下 ： Fib_Pop(H) 1 z = 2 if z !=NIL 3 for each child x of z 4 add x to the root list of H 5 = NIL 6 remove z from the root list of H 7 if z = 8 = NIL 9 else = 10 Consolidate (H) 11 = – 1 12 return z Fib_Pop 中， 3~5 行 把 z 的子節(jié)點合并到根表上去 ，第 6 行將 z 節(jié)點 從根表中去掉。 首先將最小節(jié)點的所有子節(jié)點與根表合并，然后刪除最小節(jié)點。 合并兩個斐波那契堆 由于雙向鏈表的數(shù)據(jù)結構同時根表上的節(jié)點度數(shù)無序的性質(zhì)，因此只需把兩個根表連接同時比較最小關鍵節(jié)點取其中較小的即可。 插入一個結點 首先分配并且初始化一個節(jié)點 x 然后 加入 H 的根表中。 斐波納契堆操作 斐波那契堆支持所有的堆操作，對于不涉及 Delete 的操作有 O(1)的均攤運行時間，其關鍵思想是將主鏈上的根節(jié)點的合并操作盡可能退后，來達到提高時間效率的目的。 對于一個 特 定的斐波那契堆 ，我們構造一個數(shù)據(jù)結構 H， 其中 表示堆的大小， 指向堆中最小節(jié)點。 斐波那契堆中每個節(jié)點的屬性包括： 父節(jié)點 ， 指向任一子女的指針， 左兄弟 ， 右兄弟 ， 子女的個數(shù) ， 布爾值域 。 與二項堆不同的是主鏈上的堆有序樹不必按照度數(shù)大小從小到大排列?？墒侨绻嬖?Decrease 和 Delete 操作時必然會破壞二項圖的結構。 斐波納契堆的 特點 與二項堆相似 ,斐波那契堆 也是一種可合并堆 ，是 由一組 堆有序 樹 Decrease 和構 成的集合 。斐波那契堆中 每個節(jié)點 x 包含指向父節(jié)點的指針 ， 指向任意一個子結點的 ，表示 x 的節(jié)點個數(shù)， 指向它的左兄弟的 和右兄弟的 。 偽代碼如下： Bin_Delete(H, x) 1 Bin_Decrease(H, x, infinite) 2 Bin_Pop(H) 13 第 4 章 斐波那契堆 斐波納契堆定義 斐波那契堆是計 算計科學中 中最小堆有 序樹 的集合 ， 它和 二項堆 有類似的性質(zhì) 。操作 的時間復雜度 為 。此時，將其所在結點與父結點交換關鍵字 同時將指針指向父節(jié)點。同時合并堆的時間也為 ，故整個操作 的時間復雜度 為 。 偽代碼如下： Bin_Top (H) 1 y = NIL 2 x = 3 min = infinite 4 while x != NIL 5 if min 6 min = 7 y = x 8