【正文】 heap in practical application. Keywords: binary heap, binomial heap, fibonacci heap, implementation algorithm 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 4 目錄 第 1 章 緒論 ......................................................... 5 數(shù)據(jù)結(jié)構(gòu) ......................................................................................................... 5 堆的定義和性質(zhì) ............................................................................................. 5 堆的類別 ......................................................................................................... 6 本文主要內(nèi)容 ................................................................................................. 6 第 2 章 二叉堆 ....................................................... 7 二叉堆的定義 ................................................................................................. 7 二叉堆的存儲(chǔ) ................................................................................................. 7 二叉堆的基本操作 ......................................................................................... 7 二叉堆的應(yīng)用局限性 ..................................................................................... 7 第 3 章 二項(xiàng)堆 ...................................... 錯(cuò)誤 !未定義書簽。 隨著 處理 數(shù)據(jù)規(guī)模的日益增加，如何讓程序高效穩(wěn)定運(yùn)行成為人們思考的問題。 堆的定義 堆是計(jì)算機(jī)科學(xué)中最常用的數(shù)據(jù)結(jié)構(gòu)之一。由于二叉堆要求連續(xù)的存儲(chǔ)空間，因此對(duì)于增量數(shù)據(jù)即我們無法事先預(yù)知 數(shù)據(jù)總的規(guī)模的情況下，我們無法確定應(yīng)該分配的內(nèi)存大小。本文通過學(xué)習(xí)兩種數(shù)據(jù)結(jié)構(gòu)的數(shù) 學(xué)性質(zhì)和實(shí)現(xiàn)算法給出具體的代碼實(shí)現(xiàn)，同時(shí)比較了兩種數(shù)據(jù)結(jié)構(gòu)的時(shí)間效率。 第五章 介紹具體的代碼實(shí)現(xiàn)和性能分析。因此，第 1 個(gè)位置的左右子節(jié)點(diǎn)分別在 2 和 3，第 2 個(gè)位置的左右子節(jié)點(diǎn)分別在 4 和 5，以此類推。 .上圖 (c)反應(yīng)了對(duì)于度數(shù)為 k 的二叉樹其直接的對(duì)應(yīng)的二叉樹的度數(shù)從左到右依次是 k1,k2… 0。 對(duì)于二叉堆中的每個(gè)節(jié)點(diǎn) x 包括以 下屬性：子女個(gè)數(shù)，最左孩子 ，右兄弟 ，父節(jié)點(diǎn) ， 關(guān)鍵字 。在得到的這條主鏈上度數(shù)為i 的根節(jié)點(diǎn)至多有兩個(gè)且相鄰。 偽代碼如下： Bin_Top (H) 1 y = NIL 2 x = 3 min = infinite 4 while x != NIL 5 if min 6 min = 7 y = x 8 x = 9 return y 刪除最小關(guān)鍵字 首先 先找到最小關(guān)鍵字所在結(jié)點(diǎn)，將 該節(jié)點(diǎn)的 子樹看作一個(gè)獨(dú)立的二項(xiàng)堆，再將此堆合并到原先的堆中 ，然后刪除最小關(guān)鍵節(jié)點(diǎn) 即可。 偽代碼如下： Bin_Delete(H, x) 1 Bin_Decrease(H, x, infinite) 2 Bin_Pop(H) 13 第 4 章 斐波那契堆 斐波納契堆定義 斐波那契堆是計(jì) 算計(jì)科學(xué)中 中最小堆有 序樹 的集合 ， 它和 二項(xiàng)堆 有類似的性質(zhì) 。 與二項(xiàng)堆不同的是主鏈上的堆有序樹不必按照度數(shù)大小從小到大排列。 插入一個(gè)結(jié)點(diǎn) 首先分配并且初始化一個(gè)節(jié)點(diǎn) x 然后 加入 H 的根表中。注意 這 里 并不是真正的最小結(jié)點(diǎn) 還需要調(diào)用Consolidatel 來確定最終 的值 。 減小一個(gè)關(guān)鍵字 斐波那契堆利用 級(jí)聯(lián)剪枝 的技術(shù)來維護(hù)斐波那契的性質(zhì) 。 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 18 刪除一個(gè)結(jié)點(diǎn) 刪除操作的 過程 比較 簡單， 首先 減小 對(duì)應(yīng)節(jié)點(diǎn)的關(guān)鍵字值 直到 所指向節(jié)點(diǎn)的關(guān)鍵字值小 ,此時(shí)對(duì)應(yīng)節(jié)點(diǎn)成為 , 然后 調(diào)用彈出操作函數(shù)即可。 int size。 bin_empty(),此函數(shù)返回一個(gè)布爾值來判定對(duì)應(yīng)的二項(xiàng)堆是否為空。 int mark。 fib_link(),此函數(shù)接受兩個(gè) fib_node 結(jié)構(gòu)體指針，將兩個(gè)無序的二項(xiàng)樹合并，并且返回對(duì)應(yīng)結(jié)果樹的根節(jié)點(diǎn)。在二項(xiàng)堆中為 le()，在斐波納契堆為 _le()。 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 22 第 6 章 性能測試 我們對(duì)二項(xiàng)堆和斐波那契堆的 Push 和 Pop 操作進(jìn)行測試。其中 clocks 代表 push操作耗費(fèi)的掛鐘時(shí)間， clocks 代表 pop 操作耗費(fèi)的掛鐘時(shí)間， sds 代表 push操作耗 費(fèi)了幾秒， sds 代表 pop 操作耗費(fèi)了幾秒， all 代表一次實(shí)驗(yàn)總共耗費(fèi)的時(shí)間。二項(xiàng)堆解決了離散空間上面堆的實(shí)現(xiàn)問題，與二叉堆有相同的漸近時(shí)間復(fù)雜度。 最后，感謝各位評(píng)審老師在百忙之中抽出寶貴的時(shí)間對(duì)本論文進(jìn)行審閱和參加答辯。 27 。在論文的編寫過程中，陳歡老師提出了許多的寶貴意見和建議，使我得到了很大的啟發(fā)。人們不停的在探索這種抽象數(shù)據(jù)結(jié)構(gòu)更好的實(shí)現(xiàn)算法。 通過 對(duì) 100000 個(gè)數(shù) 據(jù)進(jìn)行測試 的實(shí)驗(yàn) ， 我們 得到下列結(jié)果 。重復(fù)這個(gè)這個(gè)操作多遍，取平均值。 fib_func_test（） ,斐波納契堆的測試函數(shù)，不包括性能測試，主要是對(duì) Push,Pop和 Top 操作進(jìn)行測試。 }。 struct fib_node *child。 bin_replace(),此函數(shù)改變某個(gè)節(jié)點(diǎn)的關(guān)鍵字值，并且通過遞歸的父節(jié)點(diǎn)比較關(guān)鍵字值來維持堆的有序結(jié)構(gòu)。 }。由于 二項(xiàng)式是對(duì)稱的， 因此通過級(jí)聯(lián)減枝的技術(shù) 可以保證類使二項(xiàng)式減少一個(gè)數(shù)量級(jí) ，維持二項(xiàng)樹的形狀。 while 循環(huán)反復(fù)講相同度數(shù)的二叉樹進(jì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) 從根表中去掉。 斐波納契堆操作 斐波那契堆支持所有的堆操作，對(duì)于不涉及 Delete 的操作有 O(1)的均攤運(yùn)行時(shí)間，其關(guān)鍵思想是將主鏈上的根節(jié)點(diǎn)的合并操作盡可能退后，來達(dá)到提高時(shí)間效率的目的。可是如果存在 Decrease 和 Delete 操作時(shí)必然會(huì)破壞二項(xiàng)圖的結(jié)構(gòu)。操作 的時(shí)間復(fù)雜度 為 。由于需要合并 操作的時(shí)間復(fù)雜度為 ， 因此 插入操作 的時(shí)間復(fù)雜度為 。 偽代碼如下： Bin_Link(y, z) 1 ← z 2 ← 3 ← y 4 ← +1 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 10 上圖是如何遍歷主鏈的示意圖。 因此 以上第一個(gè)性質(zhì)保證了二項(xiàng)樹的 主鏈 包含了最小的關(guān)鍵字。 上圖 (a)反應(yīng)了怎樣由兩棵度數(shù)為 k1 的二叉樹構(gòu)造度數(shù)為 k 的二叉樹。 二叉堆存儲(chǔ) 二叉堆在內(nèi)存中連續(xù)存儲(chǔ)使用數(shù)組表示。對(duì)二項(xiàng)堆的效率分析有個(gè)比較清楚的認(rèn)識(shí)。斐波納契堆由于采用了循環(huán)雙向鏈表的數(shù)據(jù)結(jié)構(gòu) 使得在不涉及刪除操作的情況下 時(shí)間復(fù)雜度為 O(1)， 從而大大提高 時(shí)間效率。 堆的分類 從物理的角 度來 講 ，堆的節(jié)點(diǎn)在內(nèi)存中