《二项堆和Fibonacci堆的分析与实现》-毕业论文设计（学术).doc

PAGE II PAGE I l MACROBUTTON MTEditEquationSection2 SEQ MTEqn \r \h \* MERGEFORMAT SEQ MTSec \r 1 \h \* MERGEFORMAT SEQ MTChap \r 1 \h \* MERGEFORMAT 本科生毕业设计（论文） 题 目： 二项堆和Fibonacci堆的分析与实现 姓 名： 学 号： 110901004 学 院： 数学与计算机科学学院 专 业： 计算机科学与技术 年 级： 2009 级 指导教师： （签名） 年 月 日 福州大学本科生毕业设计(论文) PAGE 2 PAGE 5 二项堆和Fibonacci堆的分析与实现 摘要 堆是计算机科学中一类特殊的数据结构的统称。堆通常被视为部分有序的树形对象。 堆总是满足堆中某个节点的值总是不大于或不小于其父节点的值这个特殊性质。通常将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆的实现包括二叉堆、二项堆，斐波那契堆。堆也是计算机程序设计中经常用到的数据结构，在最短路算法的快速实现和最优编码的哈夫曼树实现中都需要用到堆. 同时堆也经常作为优先级队列来使用，在程序调度算法中发挥重要作用。斐波那契堆有着非常好的均摊运行时间，可是其数据结构和算法实现相对比较复杂，因此人们一直在寻找一种既能实现较好的均摊运行时间，同时数据结构相对比较简洁的实现算法。本课题的目的是学习连续空间上二叉堆的性质特点和离散空间上二项堆以及斐波那契堆的性质特点同时实现二项堆和斐波那契堆的具体算法。通过具体代码实现来对比二项堆和斐波那契堆实现的时间空间上消耗，对比起各自的优劣，同时探讨堆在具体应用中发挥的作用。 关键字：二叉堆，二项堆，斐波纳契堆，实现算法。 Performance analysis and Implementation for binomial heap and fibonacci heap Abstract Heap is a special kind of data structure in computer 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 computer 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 impleme