二項堆和fibonacci堆的分析與實現(xiàn)畢業(yè)設(shè)計論文-文庫吧
2025-06-03 06:35 本頁面
【正文】 作。由于這些特殊性質(zhì)，使得它在許多具體算法中得到普遍應(yīng)用，例如最短路算法的快速實現(xiàn)，最優(yōu)編碼的哈夫曼樹實現(xiàn)，優(yōu)先級調(diào)度算法等等。 堆的分類從物理的角度來講，堆的節(jié)點在內(nèi)存中可以連續(xù)分布也可以分散分布，前者是二叉堆，后者是二項堆和斐波納契堆。二叉堆的實現(xiàn)相對簡單，運行時間的常數(shù)因子也小，但是同時也存在一些不足之處。由于二叉堆要求連續(xù)的存儲空間，因此對于增量數(shù)據(jù)即我們無法事先預(yù)知數(shù)據(jù)總的規(guī)模的情況下，我們無法確定應(yīng)該分配的內(nèi)存大小。通常這種情況下我們傾向于分配一個較大的內(nèi)存，但是極有可能造成內(nèi)存的浪費，同時當(dāng)數(shù)據(jù)規(guī)模超過分配的內(nèi)存時還要重新分配內(nèi)存，其中就要涉及較大的數(shù)據(jù)復(fù)制操作，這對運行效率是極其不利的。另外一種情況下及時我們事先知道數(shù)據(jù)規(guī)模的大小，但是由于內(nèi)存有限無法分配出足夠大連續(xù)的內(nèi)存空間。由于這兩個原因使得二叉堆的應(yīng)用得到限制，許多人開始探索離散空間上實現(xiàn)堆的方法。二項堆和斐波納契堆是離散空間上堆的實現(xiàn)，克服了二叉堆要求分配連續(xù)內(nèi)存的缺點同時維持了相關(guān)操作的高效性。在漸近時間復(fù)雜度上二項堆和二叉堆的時間復(fù)雜度是相同的。斐波納契堆由于采用了循環(huán)雙向鏈表的數(shù)據(jù)結(jié)構(gòu)使得在不涉及刪除操作的情況下時間復(fù)雜度為O(1)，從而大大提高時間效率。不過由于數(shù)據(jù)結(jié)構(gòu)相對復(fù)雜，斐波那契堆的常數(shù)因子較大，在較小規(guī)模的數(shù)據(jù)上的時間優(yōu)勢并不明顯。本文通過學(xué)習(xí)兩種數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)性質(zhì)和實現(xiàn)算法給出具體的代碼實現(xiàn)，同時比較了兩種數(shù)據(jù)結(jié)構(gòu)的時間效率。 本文主要內(nèi)容本文結(jié)構(gòu)內(nèi)容安排如下： 第一章 介紹數(shù)據(jù)結(jié)構(gòu)的重要性同時引出堆這一重要數(shù)據(jù)結(jié)構(gòu)。同時給出堆的一下基本認(rèn)識。同時在本章中給出本文的結(jié)構(gòu)安排。 第二章 介紹二叉堆的結(jié)構(gòu)，數(shù)學(xué)性質(zhì)和具體的操作。 第三章 介紹二項堆的結(jié)構(gòu)，數(shù)學(xué)額性質(zhì)和基本操作的相關(guān)算法。對二項堆的效率分析有個比較清楚的認(rèn)識。 第四章 介紹斐波納契堆的數(shù)據(jù)結(jié)構(gòu)和基本操作的算法實現(xiàn)。 第五章 介紹具體的代碼實現(xiàn)和性能分析。 第六章 總結(jié)與展望 第2章 二叉堆 二叉堆定義二叉堆是一種應(yīng)用廣泛的堆結(jié)構(gòu)。二叉堆是完全二叉樹或者是近似完全二叉樹。二叉堆滿足堆特性：父節(jié)點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值，且每個節(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。當(dāng)父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。 當(dāng)父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。 二叉堆存儲二叉堆在內(nèi)存中連續(xù)存儲使用數(shù)組表示。例如，假設(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é)點的位置。 上圖反應(yīng)了二叉堆的邏輯結(jié)構(gòu)和在內(nèi)存中的物理結(jié)構(gòu)。二叉堆可以在時間內(nèi)進(jìn)行插入節(jié)點，刪除節(jié)，改變節(jié)點的值等基本操作，同時能夠在O(1)時間內(nèi)獲得最小值。第3章 二項堆二項樹是一種通過遞歸定義的有序樹，可以由以下定義得到： (1) 度數(shù)為0的二項樹只包含一個結(jié)點。(2) 度數(shù)為k的二項樹由兩棵度數(shù)為k1的二叉樹構(gòu)成，其中的一棵二叉樹的根節(jié)點成為另一棵二叉樹的最左孩子節(jié)點。上圖(a)反應(yīng)了怎樣由兩棵度數(shù)為k1的二叉樹構(gòu)造度數(shù)為k的二叉樹。上圖(b)中的二叉樹從左至右度數(shù)分別為0至4。.上圖(c)反應(yīng)了對于度數(shù)為k的二叉樹其直接的對應(yīng)的二叉樹的度數(shù)從左到右依次是k1,k2…0。因此我們得出度數(shù)為k的二項樹共有個結(jié)點，高度為k，在深度d處有個結(jié)點。二項堆是指滿足以下性質(zhì)的二項樹的集合：(1)每棵二項樹都滿足堆性質(zhì)，即任意結(jié)點關(guān)鍵字大于等于其父結(jié)點的關(guān)鍵字。(2)集合中不能有兩棵或者兩棵以上的二項樹有相同度數(shù)。上圖是含13個結(jié)點的二項堆示意圖。由于我們并不需要對二項樹的根結(jié)點進(jìn)行隨機(jī)存取的操作，我們將這些根節(jié)點按照度數(shù)從小到大的次序鏈接成一條單鏈，形成的鏈表我們稱為主鏈。因此以上第一個性質(zhì)保證了二項樹的主鏈包含了最小的關(guān)鍵字。以上第二個性質(zhì)則說明結(jié)點數(shù)為n的二項堆的根鏈上至多有棵二項樹。對于二叉堆中的每個節(jié)點x包括以下屬性：，， 。對于一個抽象的二項堆H。 合并上圖是兩棵二項樹合并的示意圖。上圖是兩個二叉堆合并的示意圖。最基本的為二個度數(shù)相同的二項樹的合并。由于二項樹根結(jié)點包含最小的關(guān)鍵字，因此在二顆樹合并時，只需比較二個根結(jié)點關(guān)鍵字的大小，其中含小關(guān)鍵字的結(jié)點成為結(jié)果樹的根結(jié)點，另一棵樹則變成結(jié)果樹的最左孩子。偽代碼如下：Bin_Link(y, z)1 ← z2 ← 3 ← y4 ← +1上圖是如何遍歷主鏈的示意圖。兩個二項堆的合并可按如下步驟進(jìn)行：因為主鏈上的根節(jié)點的度數(shù)i從小到大排列且不存在兩個相同度數(shù)的根節(jié)點在同一主鏈上，因此可以對兩個主鏈按照根節(jié)點的度數(shù)從小到大進(jìn)行遍歷合并得到一條主鏈。在得到的這條主鏈上度數(shù)為i的根節(jié)點至多有兩個且相鄰。因此我們對主鏈進(jìn)行一次遍歷，在遍歷過程中度數(shù)為i的根節(jié)點只可能有1個，2個或者3個。我們利用三個指針prev_x，x，next_x來遍歷主鏈。來如果當(dāng)前度數(shù)為i的根結(jié)只有一個或者三個則指針指向下一個節(jié)點，如果只有兩個則合并兩棵二叉樹并且將新的根節(jié)點加入主鏈。由于含有n個節(jié)點的二叉堆的主鏈長度不超過logn+1，并且我們只遍歷了兩遍主鏈，因此合并操作的時間復(fù)雜度為。偽代碼如下:Bin_Union(H)1 H = Bin_Make()2 = Bin_Merge(H1,H2)3 free objects H1 and H2 but not the lists they point to4 if == NIL5 return H6 prev_x = NIL7 x = 8 next_x = 9 while next_x != NIL10 if ( != ) or ( != NIL and == )11 prev_x = x, x = next12 else if = 13 = 14 Bin_Link(next_x, x)15 else if prev_x == NIL16 = next_x17 else18 = next_x19 Bin_Link(x, next_x)20 x = next_x21 next_x = 22 return H 插入創(chuàng)建一個只包含要插入關(guān)鍵字的堆，再將此堆與原先的二項堆進(jìn)行合并，即可得到插入后的堆。由于需要合并操作的時間復(fù)雜度為，因此插入操作的時間復(fù)雜度為。偽代碼如下：Bin_Insert(H，x)1 subH = Bin_Make()2 = = = = = NIL3 H = Bin_Union(H, subH) 查找最小關(guān)鍵字由于滿足最小堆性質(zhì)，只需對二項堆的主鏈進(jìn)行一遍遍歷即可，因為n個節(jié)點的二項堆的主鏈長度不超過logn+1，所以查找最小關(guān)鍵字操作的時間復(fù)雜度為。偽代碼如下：Bin_Top (H)1 y = NIL2 x = 3 min = infinite4 while x != NIL5 if min6 min = 7 y = x 8 x = 9 return y 刪除最小關(guān)鍵字首先先找到最小關(guān)鍵字所在結(jié)點，將該節(jié)點的子樹看作一個獨立的二項堆，再將此堆合并到原先的堆中，然后刪除最小關(guān)鍵節(jié)點即可。由于每棵樹最多有
公司管理相關(guān)推薦
鄂ICP備17016276號-1