【正文】 1 本科生畢業(yè)設計（論文） 題 目： 二項堆和 Fibonacci 堆的分析 與 實現(xiàn) 學 院： 數(shù)學與計算機科學 學院 專 業(yè)： 計算機科學與技術 福州大學本科生畢業(yè)設計 (論文 ) 2 二 項堆和 Fibonacci 堆的分析與實現(xiàn) 摘要 堆是計算機科學中一類特殊的數(shù)據(jù)結構的統(tǒng)稱。堆通常被視為部分有序的樹形對象。 堆總是滿足堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值這個特殊性質。通常將根節(jié)點最大的堆叫做最大堆或大根堆 ，根節(jié)點最小的堆叫做最小堆或小根堆。常見的堆的實現(xiàn)包括二叉堆、二項堆，斐波那契堆。堆也是計算機程序設計中經(jīng)常用到的數(shù)據(jù)結構，在最短路算法的快速實現(xiàn)和最優(yōu)編碼的哈夫曼樹實現(xiàn)中都需要用到堆 . 同時堆也經(jīng)常作為優(yōu)先級隊列來使用，在程序調度算法中發(fā)揮重要作用。斐波那契堆有著非常好的均攤運行時間，可是其數(shù)據(jù)結構和算法實現(xiàn)相對比較復雜，因此人們一直在尋找一種既能實現(xiàn)較好的均攤運行時間，同時數(shù)據(jù)結構相對比較簡潔的實現(xiàn)算法。本課題的目的是學習連續(xù)空間上二叉堆的性質特點和離散空間上二項堆以及斐波那契堆的性質特點同時實現(xiàn)二項堆 和斐波那契堆的具體算法。通過具體代碼實現(xiàn)來對比二項堆和斐波那契堆實現(xiàn)的時間空間上消耗，對比起各自的優(yōu)劣 ， 同時探討堆在具體應用中發(fā)揮的作用 。 關鍵字：二叉堆，二項堆，斐波納契堆，實現(xiàn)算法。 3 Performance analysis and Implementation for binomial heap and fibonacci heap Abstract Heap 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, 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 福州大學本科生畢業(yè)設計 (論文 ) 4 目錄 第 1 章 緒論 ......................................................... 5 數(shù)據(jù)結構 ......................................................................................................... 5 堆的定義和性質 ............................................................................................. 5 堆的類別 ......................................................................................................... 6 本文主要內容 ................................................................................................. 6 第 2 章 二叉堆 ....................................................... 7 二叉堆的定義 ................................................................................................. 7 二叉堆的存儲 ................................................................................................. 7 二叉堆的基本操作 ......................................................................................... 7 二叉堆的應用局限性 ..................................................................................... 7 第 3 章 二項堆 ...................................... 錯誤 !未定義書簽。 二項樹 .............................................................................錯誤 !未定義書簽。 二項堆 .............................................................................錯誤 !未定義書簽。 二項堆的基本操作 .........................................................錯誤 !未定義書簽。 合并 ......................................................................錯誤 !未定義書簽。 插入 ......................................................................錯誤 !未定義書簽。 查找最小關鍵字 ................................................................................ 12 刪除最小關鍵字 ..........................................................