【正文】 ...................... 12 減小關鍵字值 .................................................................................... 12 刪除節(jié)點 ............................................................................................ 12 第 4 章 斐波那契堆 .................................................. 13 斐波納契堆的定義 ....................................................................................... 13 斐波納契堆的特點 ....................................................................................... 13 斐波那契堆操作 ........................................................................................... 14 創(chuàng)建 .................................................................................................... 14 插入 .................................................................................................... 15 刪除最小關鍵字 ................................................................................ 15 減小關鍵字值 .................................................................................... 16 刪除節(jié)點 ............................................................................................ 18 第 5 章 實現(xiàn)細節(jié) .................................................... 18 二項堆代碼結(jié)構 ........................................................................................... 19 斐波納契堆代碼結(jié)構 ................................................................................... 20 其他函數(shù) ....................................................................................................... 20 第 6 章 性能分析 .................................................... 20 總結(jié)與展望 ......................................................... 22 參考文獻 ........................................................... 23 5 第 1章 緒論 在信息化時代，電子計算機在我們?nèi)粘Ｉ钪邪缪堇嬷匾淖饔谩碾娮余]件到網(wǎng)上視頻，從網(wǎng)絡游戲到三色定理證明，程序無處不在。 隨著 處理 數(shù)據(jù)規(guī)模的日益增加，如何讓程序高效穩(wěn)定運行成為人們思考的問題。此時良好的數(shù)據(jù)結(jié)構 和精心設計的算法便成為解決問題的重點。 數(shù)據(jù)結(jié)構 數(shù)據(jù)結(jié)構是計算機科學中一個普遍而又重要的概念。數(shù)據(jù)結(jié)構是指計算機內(nèi)部存儲和組織數(shù)據(jù)的方式。 通常包括鏈式數(shù)據(jù)結(jié)構比如數(shù)組，單鏈表，雙鏈表，還有循環(huán)鏈表，樹式數(shù)據(jù)結(jié)構比如二叉樹， 23 樹等等。 通過精心設計數(shù)據(jù)結(jié)構和建立在對應數(shù)據(jù)結(jié)構上的各種操作，通常情況下能夠使得程序運行的更加高效和穩(wěn)定。常見的數(shù)據(jù)結(jié)構包括紅黑樹， AVL 樹， B 樹，二叉堆，棧等等。在面對現(xiàn)實世界中的具體問題時，我們通過抽象來建立對應的數(shù)學描述，選擇合理的數(shù)據(jù)結(jié)構能夠?qū)栴}的高效解決起到事 半功倍的作用。 堆的定義 堆是計算機科學中最常用的數(shù)據(jù)結(jié)構之一。從抽象的角度來講，堆是部分有序的樹形結(jié)構。它滿足任意節(jié)點的關鍵字值總是比起父節(jié)點的關鍵字值來的小（最小堆）或者任意節(jié)點的關鍵字值總是比起父節(jié)點的關鍵來的大（最大堆）。在本文的正文部份，如果沒有特殊說明，我們總是假定在討論最小堆。它高效支持插入，彈出，刪除和改變關鍵字值的操作。由于這些特殊性質(zhì)，使得它在許多具體算法中得到普遍應用，例如最短路算法的快速實現(xiàn)，最優(yōu)編碼的哈夫曼樹實現(xiàn)，優(yōu)先級調(diào)度算法等等。 堆的分類 從物理的角 度來 講 ，堆的節(jié)點在內(nèi)存中可以連續(xù)分布也可以分散分布，前者是二叉堆，后者是二項堆和斐波納契堆。二叉堆的實現(xiàn) 相對簡單， 運行時間的常數(shù)因子也小，但是同時也存在一些不足之處。由于二叉堆要求連續(xù)的存儲空間，因此對于增量數(shù)據(jù)即我們無法事先預知 數(shù)據(jù)總的規(guī)模的情況下，我們無法確定應該分配的內(nèi)存大小。通常 這種情況下我們傾向于分配一個較大的內(nèi)存，但是極有可能造成內(nèi)存的浪費 ，同時當數(shù)據(jù)規(guī)模超過分配的內(nèi)存時還要重新分配內(nèi)存，其福州大學本科生畢業(yè)設計 (論文 ) 6 中就要涉及較大的數(shù)據(jù)復制操作，這對運行效率是極其不利的 。另外一種情況下及時我們事先知道數(shù)據(jù)規(guī)模的大小，但是 由于內(nèi)存有限 無法分配出足夠大連續(xù)的內(nèi)存空間。由于這兩個原因使得二叉堆的應用得到限制，許多人開始探索離散空間上實現(xiàn)堆的方法。 二項堆和斐波納契堆 是離散空間上堆的實現(xiàn)，克服了二叉堆要求分配連續(xù)內(nèi)存的缺點同時維持 了相關操作的高效性。在漸近時間復雜度上二項堆和二叉堆的時間復雜度是相同的。斐波納契堆由于采用了循環(huán)雙向鏈表的數(shù)據(jù)結(jié)構 使得在不涉及刪除操作的情況下 時間復雜度為 O(1)， 從而大大提高 時間效率。不過由于數(shù)據(jù)結(jié)構相對復雜，斐波那契堆的常數(shù)因子較大，在較小規(guī)模的數(shù)據(jù)上的時間優(yōu)勢并不明顯。本文通過學習兩種數(shù)據(jù)結(jié)構的數(shù) 學性質(zhì)和實現(xiàn)算法給出具體的代碼實現(xiàn)，同時比較了兩種數(shù)據(jù)結(jié)構的時間效率。 本文主要內(nèi)容 本文結(jié)構內(nèi)容安排如下： 第一章 介紹數(shù)據(jù)結(jié)構的重要性同時引出堆這一重要數(shù)據(jù)結(jié)構。同時給出堆的一下基本認識。同時在本章中給出本文的結(jié)構安排。 第二章 介紹二叉堆的結(jié)構，數(shù)學性質(zhì)和具體的操作。 第三章 介紹二項堆的結(jié)構，數(shù)學額性質(zhì)和基本操作的相關算法。對二項堆的效率分析有個比較清楚的認識。 第四章 介紹斐波納契堆的數(shù)據(jù)結(jié)構和基本操作的算法實現(xiàn)。 第五章 介紹具體的代碼實現(xiàn)和性能分析。 第六章 總結(jié)與展望 7 第 2 章 二叉堆 二叉堆定義 二叉堆是一種應用廣泛的堆結(jié)構。二叉堆是完全二叉樹或者是近似完全二叉樹。二叉堆滿足堆特性：父節(jié)點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值，且每個節(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。當父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。 當父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。 二叉堆存儲 二叉堆在內(nèi)存中連續(xù)存儲使用數(shù)組表示。例如，假設根節(jié)點在數(shù)組中的位置是 1， 則第 n 個位置的左右子節(jié)點分別在 2n和 2n+1 的位置 ，其父節(jié)點處于 n/2的位置 。因此，第 1 個位置的左右子節(jié)點分別在 2 和 3，第 2 個位置的左右子節(jié)點分別在 4 和 5，以此類推。二叉堆的連續(xù)存儲 性質(zhì) 使得我們能夠在 O(1)時間內(nèi)迅速定位父節(jié)點和子節(jié)點的位置。 上圖反應了 二叉堆的邏輯結(jié)構和在內(nèi)存中的物理結(jié)構。 二叉樹基本操作 二叉堆 可以 在 時間內(nèi) 進行插入節(jié)點 ， 刪除節(jié) ，改變 節(jié)點的值等基本操作 ，同時能夠在 O(1)時間內(nèi)獲得最小值。 福州大學本科生畢業(yè)設計 (論文 ) 8 第 3 章 二項堆 二項樹定義 二項樹是一種通過遞歸定義的有序樹，可以由以下定義得到： (1) 度數(shù)為 0 的二項樹只包含一個結(jié)點。 (2) 度數(shù)為 k 的二項樹由兩棵度數(shù)為 k1 的二叉樹構成，其中的一棵二叉樹的根節(jié)點成為另一棵二叉樹的最左孩子節(jié)點。 上圖 (a)反應了怎樣由兩棵度數(shù)為 k1 的二叉樹構造度數(shù)為 k 的二叉樹。 上圖 (b)中的二叉樹 從 左至右度數(shù)分別為 0 至 4。 .上圖 (c)反應了對于度數(shù)為 k 的二叉樹其直接的對應的二叉樹的度數(shù)從左到右依次是 k1,k2… 0。因此我們得出 度數(shù)為 k 的二項樹共有 個結(jié)點，高度為 k，在深度 d 處有 個結(jié)點。 二項堆定義