《配对堆中文版.ppt》由会员分享，可在线阅读，更多相关《配对堆中文版.ppt（34页珍藏版）》请在三一办公上搜索。
1、配对堆,Actual Complexity,配对堆,Amortized Complexity,配对堆,以上数据显示配对堆可以秒杀斐波那契堆。容易理解常数较小代码量小,定义,配对堆是一个最小(最大)配对堆是一个用指定的操作完成的最小(最大)堆,顶点结构,儿子指向儿子列表的第一个元素左、右指针用双链表作为儿子列表第一个节点的左指针指向父亲x是儿子列表的起点当且仅当x.left.son=x数据PS:无需记录父亲节点、顶点的度和被切除标记（斐波那契堆的一个标记）,合并两个最大堆,比较、链接操作比较根大小把较小的根作为较大根的子树,+,=,时间复杂度 O(1).,插入,建立一个包含要插入节点的树，然后把
2、这个树和原树合并,+,insert(2),=,插入,建立一个包含要插入节点的树，然后把这个树和原树合并,+,insert(14),=,时间复杂的 O(1).,最坏情况度数,按9,8,7.,1的顺序插入节点,最坏度数=n 1.,最坏情况高度,按1,2,3.,n的顺序插入节点,最坏高度=n.,更改节点值,因为顶点没有父亲域，所以我们不能很容易的去判断节点的值是否大于父亲所以，我们把节点脱离双向链表并与原数合并,更改节点值,如果这个节点不是根，把以它为根的子树从原树中切除出来,更改节点值,把切除的树与原树合并,1,2,6,9,2,18,3,3,更改节点值,2,18,3,3,时间复杂度 O(1).,删
3、除最大值,如果堆空，返回错误否则，删除根节点，并把所有子树合并如何合并子树好方法=平摊复杂度O(log n)坏方法=平摊复杂度O(n),用坏方法去合并子树,currentTree=first subtree.for(each of the remaining trees)currentTree=compareLink(currentTree,nextTree);,例子,删除最大值,合并成一棵树,例子,插入时间耗费 1.删除最大值的时间耗费为根的度n/2 插入(9,7,5,3,1,2,4,6,8)其次是 n/2 个移除最小值插入时间耗费 n/2.移除最大值耗费 1+2+n/2 1=Q(n2).如
4、果一次插入平摊复杂度为 O(1),移除最大值平摊就是Q(n).,用好方法合并子树,两步合并多步合并拥有相同的时间复杂度通过观察，两两合并的实际效率更好,两步合并,第一步从左到右遍历根节点的子树把子树两两合并，使子树减少一半如果包含奇数个子树，则剩余的子树跟最后的子树合并第二步从第一步完成后，最右边的子树开始从右到左，把剩余子树和最右的子树合并,两步合并举例,Pass 1,两步合并举例,Pass 2,多步合并,把所有根节点的子树放入一个队列中不断执行如下操作，直到队列中只有一个元素从队列中取出两个子树把它们合并把合并后的树放入队列,多步合并举例,多步合并举例,多步合并举例,时间复杂度O(n).,
5、删除非根元素,把这个节点从双向链表中取出使用“两步合并”或“多步合并”法合并它的子树把合并后的树与原树合并,删除元素,把节点从原树中切除,删除元素,合并这个元素的儿子,2,4,3,3,1,2,6,9,4,5,1,6,1,3,2,4,删除元素,与原树合并,1,2,6,9,4,5,1,6,1,3,2,4,2,3,3,删除元素,1,2,6,9,4,5,1,6,1,3,2,4,2,3,3,时间复杂度 O(n).,译者说明,配对堆一直是我遇到的一个比较冷门但是很实用的数据结构。它可以在O(1)的情况下做到更改元素值，如果把它套到Dijkstra上，那么Dijkstra的时间复杂度会降到O(m+n log n)而且，配对堆并不像斐波那契堆那样难写，很容易实现,译者说明,配对堆用一种很巧妙的方法，实现了如此实用的功能在某些题中，可以用配对堆去骗分（像最短路优化问题）；也可以用配对堆去改进算法总之，这个数据结构非常实用,Thank you,Email:QQ:2538244845,
