二项堆和fibonacci堆的分析与实现--大学毕业(论文)设计.doc

《二项堆和fibonacci堆的分析与实现--大学毕业(论文)设计.doc》由会员分享，可在线阅读，更多相关《二项堆和fibonacci堆的分析与实现--大学毕业(论文)设计.doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 本科生毕业设计（论文）题 目： 二项堆和Fibonacci堆的分析与实现 姓 名： 陈 伟 学 号： 110901004 学 院： 数学与计算机科学学院 专 业： 计算机科学与技术 年 级： 2009 级 指导教师： （签名） 年 月 日I二项堆和Fibonacci堆的分析与实现摘要堆是计算机科学中一类特殊的数据结构的统称。堆通常被视为部分有序的树形对象。 堆总是满足堆中某个节点的值总是不大于或不小于其父节点的值这个特殊性质。通常将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆的实现包括二叉堆、二项堆，斐波那契堆。堆也是计算机程序设计中经常用到的数据结构，在最短

2、路算法的快速实现和最优编码的哈夫曼树实现中都需要用到堆. 同时堆也经常作为优先级队列来使用，在程序调度算法中发挥重要作用。斐波那契堆有着非常好的均摊运行时间，可是其数据结构和算法实现相对比较复杂，因此人们一直在寻找一种既能实现较好的均摊运行时间，同时数据结构相对比较简洁的实现算法。本课题的目的是学习连续空间上二叉堆的性质特点和离散空间上二项堆以及斐波那契堆的性质特点同时实现二项堆和斐波那契堆的具体算法。通过具体代码实现来对比二项堆和斐波那契堆实现的时间空间上消耗，对比起各自的优劣，同时探讨堆在具体应用中发挥的作用。关键字：二叉堆，二项堆，斐波纳契堆，实现算法。Performance analy

3、sis 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 pa

4、rent . 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 whic

5、h 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 ve

6、ry 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

7、 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

8、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目录第1章 绪论51.1 数据结构51.2 堆的定义和性质51.3 堆的类别61.4 本文主要内容6第2章 二叉堆72.1 二叉堆的定义72.2 二叉堆的存储72.3 二

9、叉堆的基本操作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章

10、 性能分析20总结与展望22参考文献23第1章 绪论在信息化时代，电子计算机在我们日常生活中扮演利益重要的作用。从电子邮件到网上视频，从网络游戏到三色定理证明，程序无处不在。随着处理数据规模的日益增加，如何让程序高效稳定运行成为人们思考的问题。此时良好的数据结构和精心设计的算法便成为解决问题的重点。1.1数据结构数据结构是计算机科学中一个普遍而又重要的概念。数据结构是指计算机内部存储和组织数据的方式。通常包括链式数据结构比如数组，单链表，双链表，还有循环链表，树式数据结构比如二叉树，2-3树等等。通过精心设计数据结构和建立在对应数据结构上的各种操作，通常情况下能够使得程序运行的更加高效和稳定。

11、常见的数据结构包括红黑树，AVL树，B树，二叉堆，栈等等。在面对现实世界中的具体问题时，我们通过抽象来建立对应的数学描述，选择合理的数据结构能够对问题的高效解决起到事半功倍的作用。1.2 堆的定义堆是计算机科学中最常用的数据结构之一。从抽象的角度来讲，堆是部分有序的树形结构。它满足任意节点的关键字值总是比起父节点的关键字值来的小（最小堆）或者任意节点的关键字值总是比起父节点的关键来的大（最大堆）。在本文的正文部份，如果没有特殊说明，我们总是假定在讨论最小堆。它高效支持插入，弹出，删除和改变关键字值的操作。由于这些特殊性质，使得它在许多具体算法中得到普遍应用，例如最短路算法的快速实现，最优编码的

12、哈夫曼树实现，优先级调度算法等等。1.3 堆的分类从物理的角度来讲，堆的节点在内存中可以连续分布也可以分散分布，前者是二叉堆，后者是二项堆和斐波纳契堆。二叉堆的实现相对简单，运行时间的常数因子也小，但是同时也存在一些不足之处。由于二叉堆要求连续的存储空间，因此对于增量数据即我们无法事先预知数据总的规模的情况下，我们无法确定应该分配的内存大小。通常这种情况下我们倾向于分配一个较大的内存，但是极有可能造成内存的浪费，同时当数据规模超过分配的内存时还要重新分配内存，其中就要涉及较大的数据复制操作，这对运行效率是极其不利的。另外一种情况下及时我们事先知道数据规模的大小，但是由于内存有限无法分配出足够大

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二叉树基本操作二叉堆可以在时间内进行插入节点，删除节，改变节点的值等基本操作，

16、同时能够在O(1)时间内获得最小值。第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二项堆定义二项堆是指满足以下性质的二项树

17、的集合：(1)每棵二项树都满足堆性质，即任意结点关键字大于等于其父结点的关键字。(2)集合中不能有两棵或者两棵以上的二项树有相同度数。上图是含13个结点的二项堆示意图。由于我们并不需要对二项树的根结点进行随机存取的操作，我们将这些根节点按照度数从小到大的次序链接成一条单链，形成的链表我们称为主链。因此以上第一个性质保证了二项树的主链包含了最小的关键字。以上第二个性质则说明结点数为n的二项堆的根链上至多有棵二项树。对于二叉堆中的每个节点x包括以下属性：子女个数x.degree，最左孩子x.lchild，右兄弟x.rsibling，父节点x.par， 关键字x.key。对于一个抽象的二项堆H，H.

18、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上图是如何遍历主链的示意图。两个二项堆的合并可按如下步骤进行：因为主链上的根节点的度数i从

19、小到大排列且不存在两个相同度数的根节点在同一主链上，因此可以对两个主链按照根节点的度数从小到大进行遍历合并得到一条主链。在得到的这条主链上度数为i的根节点至多有两个且相邻。因此我们对主链进行一次遍历，在遍历过程中度数为i的根节点只可能有1个，2个或者3个。我们利用三个指针prev_x，x，next_x来遍历主链。来如果当前度数为i的根结只有一个或者三个则指针指向下一个节点，如果只有两个则合并两棵二叉树并且将新的根节点加入主链。由于含有n个节点的二叉堆的主链长度不超过logn+1，并且我们只遍历了两遍主链，因此合并操作的时间复杂度为。伪代码如下:Bin_Union(H)1 H = Bin_Mak

20、e()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 != NIL10if (x.degree != next_x.degree) or (next_x.rsibling != NIL and next_x.rsibling.degree = x.degree)11prev_x = x, x = nex

21、t12else if x.key = next_x.key13x.rsibling = next_x.rsibling14Bin_Link(next_x, x)15else if prev_x = NIL16H.head = next_x17else18prev_x.rsibling = next_x19Bin_Link(x, next_x)20x = next_x21next_x = x.rsibling22 return H3.3.2 插入创建一个只包含要插入关键字的堆，再将此堆与原先的二项堆进行合并，即可得到插入后的堆。由于需要合并操作的时间复杂度为，因此插入操作的时间复杂度为。伪代码如

22、下：Bin_Insert(H，x)1 subH = Bin_Make()2 x.par = x.lchild = x.rsibling = x.degree = subH.head = NIL3 H = Bin_Union(H, subH)3.3.3 查找最小关键字由于满足最小堆性质，只需对二项堆的主链进行一遍遍历即可，因为n个节点的二项堆的主链长度不超过logn+1，所以查找最小关键字操作的时间复杂度为。伪代码如下：Bin_Top (H)1 y = NIL2 x = H.head3 min = infinite4 while x != NIL5if x.key min6min = x.key

23、7y = x8x = x.rsibling9 return y3.3.4 删除最小关键字首先先找到最小关键字所在结点，将该节点的子树看作一个独立的二项堆，再将此堆合并到原先的堆中，然后删除最小关键节点即可。由于每棵树最多有logn+1棵子树，创建新堆的时间为。同时合并堆的时间也为，故整个操作的时间复杂度为。伪代码如下：Bin_Pop(H)1 find the node with smallest key value on main chain and remove it from main chain.2 subH = Bin_Make()3 reverse the order of the

24、linked list of xs children, set the p field of each child to NIL and set headH to the the head of the resulting list.4 H = Bin_Union(H, subH)5 return x3.3.5 减小关键字的值由于在减小关键字的值后，可能不再满足最小堆性质。此时，将其所在结点与父结点交换关键字同时将指针指向父节点。重复上述操作直到该节点为根节点或者该节点的关键值小于其父节点的关键字及最小堆性质得到满足。操作的时间复杂度为。伪代码如下：Bin_Decrease(H，x, k)1

25、x.key = k ,y = x, z = x.par2 while z !=NIL and y.key z.key3swamp x.key and y.key4y = z, z = x.par3.3.6 删除将需要删除的结点的关键字的值减小到负无穷大（比二项堆中的其他所有关键字的值都小即可），再删除最小关键字的结点即可。伪代码如下：Bin_Delete(H, x)1 Bin_Decrease(H, x, -infinite)2 Bin_Pop(H)第4章 斐波那契堆4.1斐波纳契堆定义斐波那契堆是计算计科学中中最小堆有序树的集合，它和二项堆有类似的性质。斐波那契堆不涉及删除元素的操作有O(1

26、)的平摊时间，因此如果程序中Decrease和Delete操作较少则能够获得极高效率。斐波那契堆中每个节点x包含指向父节点的指针x.par，指向任意一个子结点的x.child，表示x的节点个数x.degree，指向它的左兄弟的y.left和右兄弟的y.right。同时x的所有子节点都用双向循环链表链接起来。4.2 斐波纳契堆的特点与二项堆相似,斐波那契堆也是一种可合并堆，是由一组堆有序树Decrease和构成的集合。如果不对斐波纳契堆进行Decrease和Delete操作那么集合中的树都是二叉树。可是如果存在Decrease和Delete操作时必然会破坏二项图的结构。在这种情况下会出现树高为k

27、，结点个数少于2k的情况。与二项堆不同的是主链上的堆有序树不必按照度数大小从小到大排列。 上图是斐波那契堆的示意图。斐波那契堆中每个节点的属性包括：父节点x.par，指向任一子女的指针x.child，左兄弟x.left，右兄弟x.right，子女的个数x.degree，布尔值域x.mark。其中任意节点的所有子女被组织成循环双向链表，x.mark表示节点x成为另一个节点的子节点以来是否失去了一个孩子。对于一个特定的斐波那契堆，我们构造一个数据结构H，其中H.size表示堆的大小，H.min指向堆中最小节点。在斐波那契堆中，所有树的根节点都链接成一个环形的双链表，称为堆的根表。 4.3 斐波纳契

28、堆操作 斐波那契堆支持所有的堆操作，对于不涉及Delete的操作有O(1)的均摊运行时间，其关键思想是将主链上的根节点的合并操作尽可能退后，来达到提高时间效率的目的。4.3.1 创建一个新的斐波那契堆过程Fib_Make() 分配并初始化一个斐波那契堆对象H。4.3.2 插入一个结点 首先分配并且初始化一个节点x然后加入H的根表中。伪代码如下：Fib_Insert(H, x)1 x.degree = 0, x.par = NIL, x.child = NIL, x.left = x, x.right = x, x.mark =FALSE2 merge the root list which c

29、ontains x to root list H3 if H.min = =NIL or x.key H.min.key4 H.min = x5 H.n = H.n + 1 下图将关键字为21的结点插入斐波那契堆的示意图。4.3.3 合并两个斐波那契堆由于双向链表的数据结构同时根表上的节点度数无序的性质，因此只需把两个根表连接同时比较最小关键节点取其中较小的即可。伪代码如下：Fib_Union(H1, H2)1 H = Fib_Make()2 H.min = H1.min3 merge the root list of H2 with the root list of H4 if (H1.mi

30、n = NIL) or (H2.min != NIL and H2.min y.key9exchange 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.key2error new key is greater than current key3 x.key = k4 y = x.par5 if y != NIL

31、 and x.key y.key6CUT(H, x, y)7 CASCADING-CUT(H, y)8 if x.key H.min.key9 H.min = xCUT(H, x, y)1 remove x from the child list of y, decrementing degreey2 add x to the root list of H3 x.par = NIL4 x.mark = FALSECASCADING-CUT(H, y)1 z = y.par2 if z != NIL3 if y.mark = FALSE4 y.mark =TRUE5 else CUT(H, y,

32、 z)6 CASCADING-CUT(H, z)下图中：(a),(b)46减小为5； (c),(d),(e)35减小为5级联剪切的过程如下：当节点y被加入根链后同时检查指针y.par指向的节点，如果y.par.mark = = true那么对y.par进行级联剪切的操作，否则另y.par.mark = true，操作结束。那么为什么偶数个的时候要递归往上删除？因为度数为k的二项树在i层共有C(k, i)个结点(i= 0, 1, 2, , k)。如果不进行级联剪枝操作的话，我们可以发现删除几个节点后树的形状就会显得十分凌乱毫无章法。但是如果进行了级联剪枝，在偶数个结点时进行级联剪切时，原来是C(

33、3, 0 )= 1, C(3, 1) = 3, C(3, 2) = 3, C(3, 3) = 1, 减少两个结点关键字后，变为：C(2, 0) = 0，C(2, 1) = 2， C(2, 2) = 1;由于二项式是对称的，因此通过级联减枝的技术可以保证类使二项式减少一个数量级，维持二项树的形状。4.3.6 删除一个结点删除操作的过程比较简单，首先减小对应节点的关键字值直到H.min所指向节点的关键字值小,此时对应节点成为H.min, 然后调用弹出操作函数即可。伪代码如下：Fib_Delete(H, x)1 Fib_Decrease (H, x, -)2 Fib_Pop (H)第5章 实现细节5

34、.1二项堆代码结构二项堆涉及到的数据结构主要包括bin_node 和 bin_heap，具体定义如下：struct bin_node struct bin_node *father;struct bin_node *lchild;struct bin_node *rsibling;void *data;int degree;struct bin_heap struct bin_node *head;int size;主要涉及到的函数如下：bin_Make(),此函数分配一个bin_heap结构体指针并且初始化然后返回对应的结构体指针。bin_link(),此函数接受两个bin_node结构体指

35、针作为参数，将对应的两棵二项树合并并且返回结果树的根节点指针。bin_merge(),此函数接受两个bin_heap结构体指针作为参数，将对应的两个二项堆的主链按序合并，并将结果主链的头部指针返回。bin_Union(),此函数接受两个bin_heap结构体指针作为参数，内部调用bin_merge()合并主链，然后对主链上相同度数的节点进行进一步合并。bin_replace(),此函数改变某个节点的关键字值，并且通过递归的父节点比较关键字值来维持堆的有序结构。bin_size(),此函数返回二项堆的节点数目。bin_empty(),此函数返回一个布尔值来判定对应的二项堆是否为空。bin_del

36、ete()，此函数删除某个给定的节点，通过进一步的操作来保证二项堆的数学性质和结构。bin_Push(),bin_Pop(),bin_Top(),这些函数对堆的基本操作进行封装，提供抽象的接口。bin_func_test(),二项堆的测试函数，不包括效率测试，主要是对Push,Pop，Top接口函数的测试。5.2斐波纳契堆代码结构斐波那契堆涉及到的数据结构主要包括fib_node 和 fib_heap，具体定义如下：struct fib_node struct fib_node *left;struct fib_node *right;struct fib_node *child;struct

37、 fib_node *father;int mark;int degree;void *data;struct fib_heap struct fib_node *head;int size;主要涉及到的函数如下：fib_Make(),此函数在内存中分配一个fib_heap的结构体并且初始化，函数返回对应结构体的指针。fib_link(),此函数接受两个fib_node结构体指针，将两个无序的二项树合并，并且返回对应结果树的根节点。fib_replace(),此函数改变某个节点的关键值，同时经过级联剪切的操作的维护斐波那契堆的数学性质和结构。fib_Union(),此函数接受两个fib_heap结构体指针，将对应的斐波纳契堆合并，返回合并后的堆的根节点。_listsize(),此函数接受一个fib_heap结构体指针，通过遍历根链得到根链长度的最大度数，通过这些计算要用到的临时数组的大小。consolidate(),此函数实现级联剪切的操作。fib_Push(), fib_Pop(), fib_Top()实现对斐波那契堆的基本操作进行封装，提供抽象的接口。fib_func_test（）,斐波纳契堆的测试函数，不包括性能测试，主要是对Push,Pop和Top操作进行测试。5.3其他函数代码还涉及到的其他函数：比较函数：实现cloc