二項堆和fibonacci堆的分析與實現(xiàn)畢業(yè)設(shè)計論文-文庫吧資料
2025-06-24 06:35本頁面
【正文】 ete(H, x)1 Bin_Decrease(H, x, infinite)2 Bin_Pop(H)第4章 斐波那契堆斐波那契堆是計算計科學(xué)中中最小堆有序樹的集合，它和二項堆有類似的性質(zhì)。操作的時間復(fù)雜度為。此時，將其所在結(jié)點(diǎn)與父結(jié)點(diǎn)交換關(guān)鍵字同時將指針指向父節(jié)點(diǎ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é)點(diǎn)，將該節(jié)點(diǎn)的子樹看作一個獨(dú)立的二項堆，再將此堆合并到原先的堆中，然后刪除最小關(guān)鍵節(jié)點(diǎn)即可。由于需要合并操作的時間復(fù)雜度為，因此插入操作的時間復(fù)雜度為。由于含有n個節(jié)點(diǎn)的二叉堆的主鏈長度不超過logn+1，并且我們只遍歷了兩遍主鏈，因此合并操作的時間復(fù)雜度為。我們利用三個指針prev_x，x，next_x來遍歷主鏈。在得到的這條主鏈上度數(shù)為i的根節(jié)點(diǎn)至多有兩個且相鄰。偽代碼如下：Bin_Link(y, z)1 ← z2 ← 3 ← y4 ← +1上圖是如何遍歷主鏈的示意圖。最基本的為二個度數(shù)相同的二項樹的合并。 合并上圖是兩棵二項樹合并的示意圖。對于二叉堆中的每個節(jié)點(diǎn)x包括以下屬性：， 。因此以上第一個性質(zhì)保證了二項樹的主鏈包含了最小的關(guān)鍵字。上圖是含13個結(jié)點(diǎn)的二項堆示意圖。二項堆是指滿足以下性質(zhì)的二項樹的集合：(1)每棵二項樹都滿足堆性質(zhì)，即任意結(jié)點(diǎn)關(guān)鍵字大于等于其父結(jié)點(diǎn)的關(guān)鍵字。.上圖(c)反應(yīng)了對于度數(shù)為k的二叉樹其直接的對應(yīng)的二叉樹的度數(shù)從左到右依次是k1,k2…0。上圖(a)反應(yīng)了怎樣由兩棵度數(shù)為k1的二叉樹構(gòu)造度數(shù)為k的二叉樹。第3章 二項堆二項樹是一種通過遞歸定義的有序樹，可以由以下定義得到： (1) 度數(shù)為0的二項樹只包含一個結(jié)點(diǎn)。 上圖反應(yīng)了二叉堆的邏輯結(jié)構(gòu)和在內(nèi)存中的物理結(jié)構(gòu)。因此，第1個位置的左右子節(jié)點(diǎn)分別在2和3，第2個位置的左右子節(jié)點(diǎn)分別在4和5，以此類推。 二叉堆存儲二叉堆在內(nèi)存中連續(xù)存儲使用數(shù)組表示。當(dāng)父節(jié)點(diǎn)的鍵值總是大于或等于任何一個子節(jié)點(diǎn)的鍵值時為最大堆。二叉堆是完全二叉樹或者是近似完全二叉樹。 第五章 介紹具體的代碼實現(xiàn)和性能分析。對二項堆的效率分析有個比較清楚的認(rèn)識。 第二章 介紹二叉堆的結(jié)構(gòu)，數(shù)學(xué)性質(zhì)和具體的操作。同時給出堆的一下基本認(rèn)識。本文通過學(xué)習(xí)兩種數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)性質(zhì)和實現(xiàn)算法給出具體的代碼實現(xiàn)，同時比較了兩種數(shù)據(jù)結(jié)構(gòu)的時間效率。斐波納契堆由于采用了循環(huán)雙向鏈表的數(shù)據(jù)結(jié)構(gòu)使得在不涉及刪除操作的情況下時間復(fù)雜度為O(1)，從而大大提高時間效率。二項堆和斐波納契堆是離散空間上堆的實現(xiàn)，克服了二叉堆要求分配連續(xù)內(nèi)存的缺點(diǎn)同時維持了相關(guān)操作的高效性。另外一種情況下及時我們事先知道數(shù)據(jù)規(guī)模的大小，但是由于內(nèi)存有限無法分配出足夠大連續(xù)的內(nèi)存空間。由于二叉堆要求連續(xù)的存儲空間，因此對于增量數(shù)據(jù)即我們無法事先預(yù)知數(shù)據(jù)總的規(guī)模的情況下，我們無法確定應(yīng)該分配的內(nèi)存大小。 堆的分類從物理的角度來講，堆的節(jié)點(diǎn)在內(nèi)存中可以連續(xù)分布也可以分散分布，前者是二叉堆，后者是二項堆和斐波納契堆。它高效支持插入，彈出，刪除和改變關(guān)鍵字值的操作。它滿足任意節(jié)點(diǎn)的關(guān)鍵字值總是比起父節(jié)點(diǎn)的關(guān)鍵字值來的?。ㄗ钚《眩┗蛘呷我夤?jié)點(diǎn)的關(guān)鍵字值總是比起父節(jié)點(diǎn)的關(guān)鍵來的大（最大堆）。 堆的定義堆是計算機(jī)科學(xué)中最常用的數(shù)據(jù)結(jié)構(gòu)之一。常見的數(shù)據(jù)結(jié)構(gòu)包括紅黑樹，AVL樹，B樹，二叉堆，棧等等。通常包括鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)比如數(shù)組，單鏈表，雙鏈表，還有循環(huán)鏈表，樹式數(shù)據(jù)結(jié)構(gòu)比如二叉樹，23樹等等。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)中一個普遍而又重要的概念。隨著處理數(shù)據(jù)規(guī)模的日益增加，如何讓程序高效穩(wěn)定運(yùn)行成為人們思考的問題。Performance analysis and Implementation for binomial heap and fibonacci heapAbstractHeap is a special kind of data structure in puter 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 parent . 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 is often used in the design of puter 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 very good capitation running time, but its data structure and algorithm implementation is relatively plicated, 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 the property of the binary heap on continuous space. At the same time, l
公司管理相關(guān)推薦
鄂ICP備17016276號-1