配对堆中文版.ppt

配对堆,actual complexity,配对堆,amortized complexity,配对堆,以上数据显示配对堆可以秒杀斐波那契堆。 容易理解 常数较小 代码量小,定义,配对堆是一个最小 (最大)配对堆是一个用指定的操作完成的最小 (最大) 堆,顶点结构,儿子 指向儿子列表的第一个元素 左、右指针 用双链表作为儿子列表 第一个节点的左指针指向父亲 x是儿子列表的起点当且仅当x.left.son=x 数据 ps:无需记录父亲节点、顶点的度和被切除标记（斐波那契堆的一个标记）,合并两个最大堆,比较、链接操作 比较根大小 把较小的根作为较大根的子树,+,=,时间复杂度 o(1).,插入,建立一个包含要插入节点的树，然后把这个树和原树合并,+,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).,删除最大值,如果堆空，返回错误 否则，删除根节点，并把所有子树合并 如何合并子树 好方法 = 平摊复杂度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). 如果一次插入平摊复杂度为 o(1), 移除最大值平摊就是q(n).,用好方法合并子树,两步合并 多步合并 拥有相同的时间复杂度 通过观察，两两合并的实际效率更好,两步合并,第一步 从左到右遍历根节点的子树 把子树两两合并，使子树减少一半 如果包含奇数个子树，则剩余的子树跟最后的子树合并 第二步 从第一步完成后，最右边的子树开始 从右到左，把剩余子树和最右的子树合并,两步合并举例,pass 1,两步合并举例,pass 2,多步合并,把所有根节点的子树放入一个队列中 不断执行如下操作，直到队列中只有一个元素 从队列中取出两个子树 把它们合并 把合并后的树放入队列,多步合并举例,多步合并举例,多步合并举例,时间复杂度o(n).,删除非根元素,把这个节点从双向链表中取出 使用“两步合并”或“多步合并”法合并它的子树 把合并后的树与原树合并,删除元素,把节点从原树中切除,删除元素,合并这个元素的儿子,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) 而且，配对堆并不像斐波那契堆那样难写，很容易实现,译者说明,配对堆用一种很巧妙的方法，实现了如此实用的功能 在某些题中，可以用配对堆去骗分（像最