《二项堆和Fibonacci堆的分析与实现毕业设计论文1-(DOC 28页)》由会员分享，可在线阅读，更多相关《二项堆和Fibonacci堆的分析与实现毕业设计论文1-(DOC 28页)（34页珍藏版）》请在金锄头文库上搜索。
1、 本科生毕业设计（论文）题 目： 二项堆和Fibonacci堆的分析与实现 学 院： 数学与计算机科学学院 专 业： 计算机科学与技术 二项堆和Fibonacci堆的分析与实现摘要堆是计算机科学中一类特殊的数据结构的统称。堆通常被视为部分有序的树形对象。 堆总是满足堆中某个节点的值总是不大于或不小于其父节点的值这个特殊性质。通常将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆的实现包括二叉堆、二项堆，斐波那契堆。堆也是计算机程序设计中经常用到的数据结构，在最短路算法的快速实现和最优编码的哈夫曼树实现中都需要用到堆. 同时堆也经常作为优先级队列来使用，在程序调度算法
2、中发挥重要作用。斐波那契堆有着非常好的均摊运行时间，可是其数据结构和算法实现相对比较复杂，因此人们一直在寻找一种既能实现较好的均摊运行时间，同时数据结构相对比较简洁的实现算法。本课题的目的是学习连续空间上二叉堆的性质特点和离散空间上二项堆以及斐波那契堆的性质特点同时实现二项堆和斐波那契堆的具体算法。通过具体代码实现来对比二项堆和斐波那契堆实现的时间空间上消耗，对比起各自的优劣，同时探讨堆在具体应用中发挥的作用。关键字：二叉堆，二项堆，斐波纳契堆，实现算法。Performance analysis and Implementation for binomial heap and fibonacc
3、i heapAbstractHeap 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
4、 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
5、 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 structu
6、re and algorithm implementation is relatively complicated, 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.
7、 At the same time, learning the property and specific implementation algorithm of binomial heap and fibonacci heap on discrete space. Through specific code, we compare the time consumption and space consumption between binomial heap and fibonacci heap, and contrast their respective advantages and di
8、sadvantages. At the same time, we study the effect of heap in practical application.Keywords: binary heap, binomial heap, fibonacci heap, implementation algorithm目录第1章 绪论51.1 数据结构51.2 堆的定义和性质51.3 堆的类别61.4 本文主要内容6第2章 二叉堆72.1 二叉堆的定义72.2 二叉堆的存储72.3 二叉堆的基本操作72.4 二叉堆的应用局限性7第3章 二项堆83.1 二项树83.2 二项堆93.3 二项堆
9、的基本操作103.3.1 合并113.3.2 插入113.3.3 查找最小关键字123.3.4 删除最小关键字123.3.5 减小关键字值123.3.6 删除节点12第4章 斐波那契堆134.1 斐波纳契堆的定义134.2 斐波纳契堆的特点134.3 斐波那契堆操作144.3.1 创建144.3.2 插入154.3.3 删除最小关键字154.3.4 减小关键字值164.3.5 删除节点18第5章 实现细节185.1 二项堆代码结构195.2 斐波纳契堆代码结构205.3 其他函数20第6章 性能分析20总结与展望22参考文献23第1章 绪论在信息化时代，电子计算机在我们日常生活中扮演利益重要的
10、作用。从电子邮件到网上视频，从网络游戏到三色定理证明，程序无处不在。随着处理数据规模的日益增加，如何让程序高效稳定运行成为人们思考的问题。此时良好的数据结构和精心设计的算法便成为解决问题的重点。1.1数据结构数据结构是计算机科学中一个普遍而又重要的概念。数据结构是指计算机内部存储和组织数据的方式。通常包括链式数据结构比如数组，单链表，双链表，还有循环链表，树式数据结构比如二叉树，2-3树等等。通过精心设计数据结构和建立在对应数据结构上的各种操作，通常情况下能够使得程序运行的更加高效和稳定。常见的数据结构包括红黑树，AVL树，B树，二叉堆，栈等等。在面对现实世界中的具体问题时，我们通过抽象来建立
11、对应的数学描述，选择合理的数据结构能够对问题的高效解决起到事半功倍的作用。1.2 堆的定义堆是计算机科学中最常用的数据结构之一。从抽象的角度来讲，堆是部分有序的树形结构。它满足任意节点的关键字值总是比起父节点的关键字值来的小（最小堆）或者任意节点的关键字值总是比起父节点的关键来的大（最大堆）。在本文的正文部份，如果没有特殊说明，我们总是假定在讨论最小堆。它高效支持插入，弹出，删除和改变关键字值的操作。由于这些特殊性质，使得它在许多具体算法中得到普遍应用，例如最短路算法的快速实现，最优编码的哈夫曼树实现，优先级调度算法等等。1.3 堆的分类从物理的角度来讲，堆的节点在内存中可以连续分布也可以分散
12、分布，前者是二叉堆，后者是二项堆和斐波纳契堆。二叉堆的实现相对简单，运行时间的常数因子也小，但是同时也存在一些不足之处。由于二叉堆要求连续的存储空间，因此对于增量数据即我们无法事先预知数据总的规模的情况下，我们无法确定应该分配的内存大小。通常这种情况下我们倾向于分配一个较大的内存，但是极有可能造成内存的浪费，同时当数据规模超过分配的内存时还要重新分配内存，其中就要涉及较大的数据复制操作，这对运行效率是极其不利的。另外一种情况下及时我们事先知道数据规模的大小，但是由于内存有限无法分配出足够大连续的内存空间。由于这两个原因使得二叉堆的应用得到限制，许多人开始探索离散空间上实现堆的方法。二项堆和斐波
13、纳契堆是离散空间上堆的实现，克服了二叉堆要求分配连续内存的缺点同时维持了相关操作的高效性。在渐近时间复杂度上二项堆和二叉堆的时间复杂度是相同的。斐波纳契堆由于采用了循环双向链表的数据结构使得在不涉及删除操作的情况下时间复杂度为O(1)，从而大大提高时间效率。不过由于数据结构相对复杂，斐波那契堆的常数因子较大，在较小规模的数据上的时间优势并不明显。本文通过学习两种数据结构的数学性质和实现算法给出具体的代码实现，同时比较了两种数据结构的时间效率。1.4 本文主要内容本文结构内容安排如下：第一章 介绍数据结构的重要性同时引出堆这一重要数据结构。同时给出堆的一下基本认识。同时在本章中给出本文的结构安排
14、。第二章 介绍二叉堆的结构，数学性质和具体的操作。第三章 介绍二项堆的结构，数学额性质和基本操作的相关算法。对二项堆的效率分析有个比较清楚的认识。第四章 介绍斐波纳契堆的数据结构和基本操作的算法实现。第五章 介绍具体的代码实现和性能分析。第六章 总结与展望第2章 二叉堆2.1 二叉堆定义二叉堆是一种应用广泛的堆结构。二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个
15、子节点的键值时为最小堆。2.2 二叉堆存储二叉堆在内存中连续存储使用数组表示。例如，假设根节点在数组中的位置是1，则第n个位置的左右子节点分别在2n和 2n+1的位置，其父节点处于n/2的位置。因此，第1个位置的左右子节点分别在2和3，第2个位置的左右子节点分别在4和5，以此类推。二叉堆的连续存储性质使得我们能够在O(1)时间内迅速定位父节点和子节点的位置。 上图反应了二叉堆的逻辑结构和在内存中的物理结构。2.3二叉树基本操作二叉堆可以在时间内进行插入节点，删除节，改变节点的值等基本操作，同时能够在O(1)时间内获得最小值。第3章 二项堆3.1二项树定义二项树是一种通过递归定义的有序树，可以由以下定义得到： (1) 度数为0的二项树只包含一个结点。(2) 度数为k的二项树由两棵度数
