【正文】 cial 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, learning the property and specific implementation algorithm of binomial heap and fibonacci heap on discrete space. Through specific code, we pare the time consumption and space consumption between binomial heap and fibonacci heap, and contrast their respective advantages and disadvantages. At the same time, we study the effect of heap in practical application. Keywords: binary heap, binomial heap, fibonacci heap, implementation algorithm 福州大學(xué)本科生畢業(yè)設(shè)計 (論文 ) 4 目錄 第 1 章 緒論 ......................................................... 5 數(shù)據(jù)結(jié)構(gòu) ......................................................................................................... 5 堆的定義和性質(zhì) ............................................................................................. 5 堆的類別 ......................................................................................................... 6 本文主要內(nèi)容 ................................................................................................. 6 第 2 章 二叉堆 ....................................................... 7 二叉堆的定義 ................................................................................................. 7 二叉堆的存儲 ................................................................................................. 7 二叉堆的基本操作 ......................................................................................... 7 二叉堆的應(yīng)用局限性 ..................................................................................... 7 第 3 章 二項堆 ...................................... 錯誤 !未定義書簽。斐波那契堆有著非常好的均攤運(yùn)行時間，可是其數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)相對比較復(fù)雜，因此人們一直在尋找一種既能實(shí)現(xiàn)較好的均攤運(yùn)行時間，同時數(shù)據(jù)結(jié)構(gòu)相對比較簡潔的實(shí)現(xiàn)算法。 堆總是滿足堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值這個特殊性質(zhì)。堆通常被視為部分有序的樹形對象。堆也是計算機(jī)程序設(shè)計中經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)，在最短路算法的快速實(shí)現(xiàn)和最優(yōu)編碼的哈夫曼樹實(shí)現(xiàn)中都需要用到堆 . 同時堆也經(jīng)常作為優(yōu)先級隊列來使用，在程序調(diào)度算法中發(fā)揮重要作用。 關(guān)鍵字：二叉堆，二項堆，斐波納契堆，實(shí)現(xiàn)算法。 二項堆的基本操作 .........................................................錯誤 !未定義書簽。從電子郵件到網(wǎng)上視頻，從網(wǎng)絡(luò)游戲到三色定理證明，程序無處不在。數(shù)據(jù)結(jié)構(gòu)是指計算機(jī)內(nèi)部存儲和組織數(shù)據(jù)的方式。在面對現(xiàn)實(shí)世界中的具體問題時，我們通過抽象來建立對應(yīng)的數(shù)學(xué)描述，選擇合理的數(shù)據(jù)結(jié)構(gòu)能夠?qū)栴}的高效解決起到事 半功倍的作用。在本文的正文部份，如果沒有特殊說明，我們總是假定在討論最小堆。二叉堆的實(shí)現(xiàn) 相對簡單， 運(yùn)行時間的常數(shù)因子也小，但是同時也存在一些不足之處。由于這兩個原因使得二叉堆的應(yīng)用得到限制，許多人開始探索離散空間上實(shí)現(xiàn)堆的方法。不過由于數(shù)據(jù)結(jié)構(gòu)相對復(fù)雜，斐波那契堆的常數(shù)因子較大，在較小規(guī)模的數(shù)據(jù)上的時間優(yōu)勢并不明顯。同時在本章中給出本文的結(jié)構(gòu)安排。 第四章 介紹斐波納契堆的數(shù)據(jù)結(jié)構(gòu)和基本操作的算法實(shí)現(xiàn)。二叉堆滿足堆特性：父節(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點(diǎn)的鍵值，且每個節(jié)點(diǎn)的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。例如，假設(shè)根節(jié)點(diǎn)在數(shù)組中的位置是 1， 則第 n 個位置的左右子節(jié)點(diǎn)分別在 2n和 2n+1 的位置 ，其父節(jié)點(diǎn)處于 n/2的位置 。 二叉樹基本操作 二叉堆 可以 在 時間內(nèi) 進(jìn)行插入節(jié)點(diǎn) ， 刪除節(jié) ，改變 節(jié)點(diǎn)的值等基本操作 ，同時能夠在 O(1)時間內(nèi)獲得最小值。 上圖 (b)中的二叉樹 從 左至右度數(shù)分別為 0 至 4。 (2)集合中 不能有兩棵或者兩棵以上的二項樹有相同度數(shù)。以上第二個性質(zhì)則說明結(jié)點(diǎn)數(shù)為 n 的二項堆 的根鏈上至多 有棵二項樹。 上圖是兩個二叉堆合并的示意圖。 兩個二項堆的合并可按如下步驟進(jìn)行： 因?yàn)橹麈溕系母?jié)點(diǎn)的 度數(shù) i 從小到大排列且不存在兩個相同度數(shù)的根節(jié)點(diǎn)在同一主鏈上，因此可以對兩個主鏈按照根節(jié)點(diǎn)的度數(shù)從小到大進(jìn)行遍歷合并得到一條主鏈。來如果當(dāng)前度數(shù)為 i的根結(jié)只有一個或者三個則指針指向下一個節(jié)點(diǎn)，如果只有兩個則合并兩棵二叉樹并且將新的根節(jié)點(diǎn)加入主鏈。 偽代碼如下： Bin_Insert(H， x) 1 subH = Bin_Make() 2 = = = = = NIL 3 H = Bin_Union(H, subH) 查找最小關(guān)鍵字 由于滿足最小堆性質(zhì)，只需 對二項堆的主鏈進(jìn)行一遍遍歷 即可， 因?yàn)?n 個節(jié)點(diǎn)的二項堆的主鏈長度不超過 logn+1，所以查找 最小關(guān)鍵字操作的時間復(fù)雜度為。偽代碼如下： Bin_Pop(H) 1 find the node with smallest key value on main chain and remove it from main chain.