二项堆和Fibonacci堆的分析与实现

哈尔滨工业大学本科毕业设计（论文）111本科生毕业设计（论文）题 目： 二项堆和 Fibonacci 堆的分析与实现 姓 名： 学 号： 学 院： 数学与计算机科学学院 专 业： 计算机科学与技术 年 级： 指导教师： （签名）年 月 日哈尔滨工业大学本科毕业设计（论文）2二项堆和 Fibonacci 堆的分析与实现摘要堆是计算机科学中一类特殊的数据结构的统称。堆通常被视为部分有序的树形对象。 堆总是满足堆中某个节点的值总是不大于或不小于其父节点的值这个特殊性质。通常将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆的实现包括二叉堆、二项堆，斐波那契堆。堆也是计算机程序设计中经常用到的数据结构，在最短路算法的快速实现和最优编码的哈夫曼树实现中都需要用到堆. 同时堆也经常作为优先级队列来使用，在程序调度算法中发挥重要作用。斐波那契堆有着非常好的均摊运行时间，可是其数据结构和算法实现相对比较复杂，因此人们一直在寻找一种既能实现较好的均摊运行时间，同时数据结构相对比较简洁的实现算法。本课题的目的是学习连续空间上二叉堆的性质特点和离散空间上二项堆以及斐波那契堆的性质特点同时实现二项堆和斐波那契堆的具体算法。通过具体代码实现来对比二项堆和斐波那契堆实现的时间空间上消耗，对比起各自的优劣，同时探讨堆在具体应用中发挥的作用。关键字：二叉堆，二项堆，斐波纳契堆，实现算法。哈尔滨工业大学本科毕业设计（论文）3Performance analysis and Implementation for binomial heap and fibonacci 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 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 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. 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 disadvantages. At the same time, we study the effect of heap in practical application.Keywords: binary heap, binomial heap, fibonacci heap, implementation algorithm哈尔滨工业大学本科毕业设计（论文）4目录第 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 二项堆的基本操作 .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哈尔滨工业大学本科毕业设计（论文）5第 1 章 绪论在信息化时代，电子计算机在我们日常生活中扮演利益重要的作用。从电子邮件到网上视频，从网络游戏到三色定理证明，程序无处不在。随着处理数据规模的日益增加，如何让程序高效稳定运行成为人们思考的问题。此时良好的数据结构和精心设计的算法便成为解决问题的重点。1.1 数据结构数据结构是计算机科学中一个普遍而又重要的概念。数据结构是指计算机内部存储和组织数据的方式。通常包括链式数据结构比如数组，单链表，双链表，还有循环链表，树式数据结构比如二叉树，2-3 树等等。通过精心设计数据结构和建立在对应数据结构上的各种操作，通常情况下能够使得程序运行的更加高效和稳定。常见的数据结构包括红黑树，AVL 树，B 树，二叉堆，栈等等。在面对现实世界中的具体问题时，我们通过抽象来建立对应的数学描述，选择合理的数据结构能够对问题的高效解决起到事半功倍的作用。1.2 堆的定义堆是计算机科学中最常用的数据结构之一。从抽象的角度来讲，堆是部分有序的树形结构。它满足任意节点的关键字值总是比起父节点的关键字值来的小（最小堆）或者任意节点的关键字值总是比起父节点的关键来的大（最大堆） 。在本文的正文部份，如果没有特殊说明，我们总是假定在讨论最小堆。它高效支持插入，弹出，删除和改变关键字值的操作。由于这些特殊性质，使得它在许多具体算法中得到普遍应用，例如最短路算法的快速实现，最优编码的哈夫曼树实现，优先级调度算法等等。1.3 堆的分类从物理的角度来讲，堆的节点在内存中可以连续分布也可以分散分布，前者是二叉堆，后者是二项堆和斐波纳契堆。二叉堆的实现相对简单，运行时间的常数因子也小，但是同时也存在一些不足之处。由于二叉堆要求连续的存储空间，因此对于增量数据即我们无法事先预知数据总的规模的情况下，我们无法确定应该分配的内存大小。通常这种情况下我们倾向于分配一个较大的内存，但是极有可能造成内存的浪费，同时当数据规模超过分配的内存时还要重新分哈尔滨工业大学本科毕业设计（论文）6配内存，其中就要涉及较大的数据复制操作，这对运行效率是极其不利的。另外一种情况下及时我们事先知道数据规模的大小，但是由于内存有限无法分配出足够大连续的内存空间。由于这两个原因使得二叉堆的应用得到限制，许多人开始探索离散空间上实现堆的方法。二项堆和斐波纳契堆是离散空间上堆的实现，克服了二叉堆要求分配连续内存的缺点同时维持了相关操作的高效性。在渐近时间复杂度上二项堆和二叉堆的时间复杂度是相同的。斐波纳契堆由于采用了循环双向链表的数据结构使得在不涉及删除操作的情况下时间复杂度为 O(1)，从而大大提高时间效率。不过由于数据结构相对复杂，斐波那契堆的常数因子较大，在较小规模的数据上的时间优势并不明显。本文通过学习两种数据结构的数学性质和实现算法给出具体的代码实现，同时比较了两种数据结构的时间效率。1.4 本文主要内容本文结构内容安排如下：第一章 介绍数据结构的重要性同时引出堆这一重要数据结构。同时给出堆的一下基本认识。同时在本章中给出本文的结构安排。第二章 介绍二叉堆的结构，数学性质和具体的操作。第三章 介绍二项堆的结构，数学额性质和基本操作的相关算法。对二项堆的效率分析有个比较清楚的认识。第四章 介绍斐波纳契堆的数据结构和基本操作的算法实现。第五章 介绍具体的代码实现和性能分析。第六章 总结与展望哈尔滨工业大学本科毕业设计（论文）7第 2 章 二叉堆2.1 二叉堆定义二叉堆是一种应用广泛的堆结构。二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆） 。当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。2.2 二叉堆存储二叉堆在内存中连续存储使用数组表示。例如，假设根节点在数组中的位置是 1，则第 n 个位置的左右子节点分别在 2n 和 2n+1 的位置，其父节点处于n/2 的位置。因此，第 1 个位置的左右子节点分别在 2 和 3，第 2 个位置的左右子节点分别在 4 和 5，以此类推。二叉堆的连续存储性质使得我们能够在 O(1)时间内迅速定位父节点和子节点的位置。上图反应了二叉堆的逻辑结构和在内存中的物理结构。2.3 二叉树基本操作二叉堆可以在 时间内进行插入节点，删除节，改变节点的值等基本操作，同时能够在 O(1)时间内获得最小值。哈尔滨工业大学本科毕业设计（论文）8第 3 章 二项堆3.1 二项树定义二项树是一种通过递归定义的有序树，可以由以下定义得到：(1) 度数为 0 的二项树只包含一个结点。(2) 度数为 k 的二项树由两棵度数为 k-1 的二叉树构成，其中的一棵二叉树的根节点成为另一棵二叉树的最左孩子节点。上图(a)反应了怎样由两棵度数为 k-1 的二叉树构造度数为 k 的二叉树。上图(b)中的二叉树从左至右度数分别为 0 至 4。.上图(c)反应了对于度数为 k 的二叉树其直接的对应的二叉树的度数从左到右依次是 k-1,k-20。因此我们得出度数为 k 的二项树共有 个结点，高度为k，在深度 d 处有 个结点。3.2 二项堆定义二项堆是指满足以下性质的二项树的集合：(1)每棵二项树都满足堆性质，即任意结点关键字大于等于其父结点的关键字。(2)集合中不能有两棵或者两棵以上的二项树有相同度数。上图是含 13 个结点的二项堆示意图。由于我们并不需要对二项树的根结点哈尔滨工业大学本科毕业设计（论文）9进行随机存取的操作，我们将这些根节点按照度数从小到大的次序链接成一条单链，形成的链表我们称为主链。因此以上第一个性质保证了二项树的主链包含了最小的关键字。以上第二个性质则说明结点数为 n 的二项堆的根链上至多有 棵二项树。对于二叉堆中的每个节点 x 包括以下属性：子女个数x.degree，最左孩子 x.lchild，右兄弟 x.rsibling，父节点 x.par， 关键字 x.key。对于一个抽象的二项堆 H，H.head 表示主链首部，H.size 表示堆中节点的个数。3.3 二项堆的操作3.3.1 合并上图是两棵二项树合并的示意图。上图是两个二叉堆合并的示意图。最基本的为二个度数相同的二项树的合并。由于二项树根结点包含最小的关键字，因此在二颗树合并时，只需比较二个根结点关键字的大小，其中含小关键字的结点成为结果树的根结点，另一棵树则变成结果树的最左孩子。伪代码如下：Bin_Link(y, z)1 y.par z2 y.rsibling z.lchild3 z.lchild y4 z.degree z.degree+1哈尔滨工业大学本科毕业设计（论文）10上图是如何遍历主链的示意图。两个二项堆的合并可按如下步骤进行：因为主链上的根节点的度数 i 从小到大排列且不存在两个相同度数的根节点在同一主链上，因此可以对两个主链按照根节点的度数从小到大进行遍历合并得到一条主链。在得到的这条主链上度数为 i 的根节点至多有两个且相邻。因此我们对主链进行一次遍历，在遍历过程中度数为 i 的根节点只可能有 1 个，2 个或者 3 个。我们利用三个指针prev_x，x，next_x 来遍历主链。来如果当前度数为 i 的根结只有一个或者三个则指针指向下一个节点，如果只有两个则合并两棵二叉树并且将新的根节点加入主链。由于含有 n 个节点的二叉堆的主链长度不超过 logn+1，并且我们只遍历了两遍主链，因此合并操作的时间复杂度为 。伪代码如下:Bin_Union(H)1 H = Bin_Make()2 H.head = Bin_Merge(H1,H2)3 free objects H1 and H2 but not the lists they point to4 if H.head = NIL5 return H6 prev_x = NIL7 x = H.head8 next_x = x.rsibling9 while next_x != NIL10 if (x.degree != next_x.degree) or (next_x.rsibling != NIL and next_x.rsibling.degree = x.degree)11 prev_x = x, x = next12 else if x.key y.key9 exchange x y10 Fib_Link(H, y, x)11 Ad = NIL12 d = d + 113 Ad = x14 H.min = NIL15 for i = 0 to D(H.n)16 do if Ai NIL17 add Ai to the root list of H18 if H.min = NIL or Ai.key x.key2 error new key is greater than current key3 x.key = k4 y = x.par哈尔滨工业大学本科毕业设计（论文）175 if y != NIL and x.key clocks scnds clocks scnds clocks scnds clocks 代表push 操作耗费的挂钟时间，scnds 代表 push 操作耗费了几秒， scnds 代表 pop 操作耗费了几秒， all 代表一次实验总共耗费的时间。哈尔滨工业大学本科毕业设计（论文）24总结与展望数据结构和算法设计是一门创造性的学问，需要良好的数学背景和清晰的逻辑思维同时对抽象现实问题的能力提出很高的要求。面对日益增加的数据处理规模，常规的数据结构和算法无法满足运行时间的要求。因此精心设计的数据结构和实现算法成为解决问题的利器。从计算机科学诞生伊始，数据结构和算法设计也随之产生，一代一代的计算机科学家，工程师为了解决问题提出了许许多多的精巧的数据结构和算法设计。堆作为一种应用广泛的数据结构，得到许多人研究。人们不停