【正文】 福州大學(xué)本科生畢業(yè)設(shè)計 (論文 ) 2 二 項堆和 Fibonacci 堆的分析與實現(xiàn) 摘要 堆是計算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。常見的堆的實現(xiàn)包括二叉堆、二項堆，斐波那契堆。通過具體代碼實現(xiàn)來對比二項堆和斐波那契堆實現(xiàn)的時間空間上消耗，對比起各自的優(yōu)劣 ， 同時探討堆在具體應(yīng)用中發(fā)揮的作用 。 二項堆 .............................................................................錯誤 !未定義書簽。 查找最小關(guān)鍵字 ................................................................................ 12 刪除最小關(guān)鍵字 ................................................................................ 12 減小關(guān)鍵字值 .................................................................................... 12 刪除節(jié)點(diǎn) ............................................................................................ 12 第 4 章 斐波那契堆 .................................................. 13 斐波納契堆的定義 ....................................................................................... 13 斐波納契堆的特點(diǎn) ....................................................................................... 13 斐波那契堆操作 ........................................................................................... 14 創(chuàng)建 .................................................................................................... 14 插入 .................................................................................................... 15 刪除最小關(guān)鍵字 ................................................................................ 15 減小關(guān)鍵字值 .................................................................................... 16 刪除節(jié)點(diǎn) ............................................................................................ 18 第 5 章 實現(xiàn)細(xì)節(jié) .................................................... 18 二項堆代碼結(jié)構(gòu) ........................................................................................... 19 斐波納契堆代碼結(jié)構(gòu) ................................................................................... 20 其他函數(shù) ....................................................................................................... 20 第 6 章 性能分析 .................................................... 20 總結(jié)與展望 ......................................................... 22 參考文獻(xiàn) ........................................................... 23 5 第 1章 緒論 在信息化時代，電子計算機(jī)在我們?nèi)粘Ｉ钪邪缪堇嬷匾淖饔谩? 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)中一個普遍而又重要的概念。常見的數(shù)據(jù)結(jié)構(gòu)包括紅黑樹， AVL 樹， B 樹，二叉堆，棧等等。它滿足任意節(jié)點(diǎn)的關(guān)鍵字值總是比起父節(jié)點(diǎn)的關(guān)鍵字值來的?。ㄗ钚《眩┗蛘呷我夤?jié)點(diǎn)的關(guān)鍵字值總是比起父節(jié)點(diǎn)的關(guān)鍵來的大（最大堆）。 堆的分類 從物理的角 度來 講 ，堆的節(jié)點(diǎn)在內(nèi)存中可以連續(xù)分布也可以分散分布，前者是二叉堆，后者是二項堆和斐波納契堆。另外一種情況下及時我們事先知道數(shù)據(jù)規(guī)模的大小，但是 由于內(nèi)存有限 無法分配出足夠大連續(xù)的內(nèi)存空間。斐波納契堆由于采用了循環(huán)雙向鏈表的數(shù)據(jù)結(jié)構(gòu) 使得在不涉及刪除操作的情況下 時間復(fù)雜度為 O(1)， 從而大大提高 時間效率。同時給出堆的一下基本認(rèn)識。對二項堆的效率分析有個比較清楚的認(rèn)識。二叉堆是完全二叉樹或者是近似完全二叉樹。 二叉堆存儲 二叉堆在內(nèi)存中連續(xù)存儲使用數(shù)組表示。 上圖反應(yīng)了 二叉堆的邏輯結(jié)構(gòu)和在內(nèi)存中的物理結(jié)構(gòu)。 上圖 (a)反應(yīng)了怎樣由兩棵度數(shù)為 k1 的二叉樹構(gòu)造度數(shù)為 k 的二叉樹。 二項堆定義 二項堆是指滿足以下性質(zhì)的二項樹的集合： (1)每棵二項樹都滿足堆性質(zhì)，即任意結(jié)點(diǎn)關(guān)鍵字大于等于其父結(jié)點(diǎn)的關(guān)鍵字。 因此 以上第一個性質(zhì)保證了二項樹的 主鏈 包含了最小的關(guān)鍵字。 二項堆的操作 合并 上圖是兩棵二項樹合并的示意圖。 偽代碼如下： Bin_Link(y, z) 1 ← z 2 ← 3 ← y 4 ← +1 福州大學(xué)本科生畢業(yè)設(shè)計 (論文 ) 10 上圖是如何遍歷主鏈的示意圖。我們利用三個指針 prev_x， x， next_x來遍歷主鏈。由于需要合并 操作的時間復(fù)雜度為 ， 因此 插入操作 的時間復(fù)雜度為 。同時合并堆的時間也為 ，故整個操作 的時間復(fù)雜度 為 。操作 的時間復(fù)雜度 為 。斐波那契堆中 每個節(jié)點(diǎn) x 包含指向父節(jié)點(diǎn)的指針 ， 指向任意一個子結(jié)點(diǎn)的 ，表示 x 的節(jié)點(diǎn)個數(shù)， 指向它的左兄弟的 和右兄弟的 ?？墒侨绻嬖?Decrease 和 Delete 操作時必然會破壞二項圖的結(jié)構(gòu)。 斐波那契堆中每個節(jié)點(diǎn)的屬性包括： 父節(jié)點(diǎn) ， 指向任一子女的指針， 左兄弟 ， 右兄弟 ， 子女的個數(shù) ， 布爾值域 。 斐波納契堆操作 斐波那契堆支持所有的堆操作，對于不涉及 Delete 的操作有 O(1)的均攤運(yùn)行時間，其關(guān)鍵思想是將主鏈上的根節(jié)點(diǎn)的合并操作盡可能退后，來達(dá)到提高時間效率的目的。 合并兩個斐波那契堆 由于雙向鏈表的數(shù)據(jù)結(jié)構(gòu)同時根表上的節(jié)點(diǎn)度數(shù)無序的性質(zhì)，因此只需把兩個根表連接同時比較最小關(guān)鍵節(jié)點(diǎn)取其中較小的即可。偽代碼 如下 ： 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é)點(diǎn)合并到根表上去 ，第 6 行將 z 節(jié)點(diǎn) 從根表中去掉。 Consolidate 過程要做的工作是 通過遍歷一遍根鏈?zhǔn)沟糜邢嗤葦?shù)的根節(jié)點(diǎn)合福州大學(xué)本科生畢業(yè)設(shè)計 (論文 ) 16 并，最終使得根鏈上不存在度數(shù)相同的根節(jié)點(diǎn)。 while 循環(huán)反復(fù)講相同度數(shù)的二叉樹進(jìn)行連接操作 。 偽代碼如下： 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