二项堆与斐波那契堆剖析.pptx

理想王国的数据结构 ——二项堆与斐波那契堆 Binomial Heap Fibonacci Heap 广西柳州高级中学 王启圣 liouzhou_101 河北石家庄二中 李煜东 lydrainbowcat Part 1 二项堆 广西柳州高级中学 王启圣 二项堆是神马 在计算机科学中，二项堆（binomial heap）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（mergeable heap）抽象数据类型的一种。 二项堆有神马用 堆，就是用来维护一堆关键字的最值，插入一个关键字，以及删除最值。 用一般的二叉堆不就可以了么？二项堆有神马用？ 二项堆有神马用 假若用二叉堆来启发式合并一堆东西的话时间复杂度就是O(Nlog2N)。 二项堆是可合并堆，时间复杂度可以做到O(NlogN)。 fibonacci堆的思想是基于二项堆的，今晚的主角是fibonacci堆，所以自然要说下二项堆啦~~~ 二项树 我们先定义一下二项树的概念。 二项树是一种通过递归定义的有序树，可以由以下定义得到： 度数为0的二项树只包含一个结点 度数为k的二项树有一个根结点，根结点下有k个子女，每个子女分别是度数为0,1,2,…,k-2,k-1的二项树的根。 二项树 度数为k的二项树共有2k个结点，高度为k。 在深度d处有 Cnd（二项式系数）个结点，n是节点总数。 二项堆 二项堆是指满足以下性质的二项树的集合： 每棵二项树都满足最小堆性质，即结点关键字大于等于其父结点的关键字 不能有两棵或以上的二项树有相同度数（包括度数为0） 以上第一个性质保证了二项树的根结点包含了最小的关键字。第二个性质则说明结点数为N的二项堆最多只有log N+1棵二项树。 二项堆的基本操作 合并 插入 查找 删除 二项堆的基本操作——合并 合并 插入 查找 删除 二项堆的基本操作——合并 最基本的就是两个度数相同的二项树的合并。 由于二项树根结点包含最小的关键字，因此在二颗树合并时，只需比较二个根结点关键字的大小，其中含小关键字的结点成为结果树的根结点，另一棵树则变成结果树的子树。时间复杂度为O(1)。 这样，实际上就是把两个度数为k的二项树合并为一个度数为k+1的二项树。 二项堆的基本操作——合并 现在是合并两个二项堆。 两个二项堆的合并则可按如下步骤进行：度数k从小取到大，在两个二项堆中如果其中只有一棵树的度数为k，即将此树移动到结果堆，而如果两棵树的度数都为k，则根据以上方法合并为一个度数为k+1的二项树。此后这个度数为k+1的树将可能会和其他度数为k+1的二项树进行合并。 此操作的时间复杂度为O(logN)。 二项堆的基本操作——插入 合并 插入 查找 删除 二项堆的基本操作——插入 创建一个只包含要插入关键字的堆，再将此堆与原先的二项堆进行合并，即可得到插入后的堆。 由于需要合并，插入操作需要O(logN)的时间。 二项堆的基本操作——查找 合并 插入 查找 删除 二项堆的基本操作——查找 查找最小元素。 由于满足最小堆性质，只需查找二项树的的根结点即可，而二项堆有O(logN)棵二项树，因此时间复杂度为O(logN)。 二项堆的基本操作——删除 合并 插入 查找 删除 二项堆的基本操作——删除 删除最小元素。 先找到最小关键字所在结点，然后将它从其所在的二项树中删除，并获得其子树。将这些子树看作一个独立的二项堆，再将此堆合并到原先的堆中即可。由于每棵树最多有O(logN)棵子树，创建新堆的时间为O(logN)。同时合并堆的时间也为O(logN)，故整个操作所需时间为O(logN) 。 例题 ZOJ 2334 Monkey King 有N个互相独立的数值分别属于N个集合。 有M次操作，每次操作的对象是两个不同的集合A和B，把A和B中的最大值都减少一半，然后合并两个集合，并询问该集合当前最大值。 例题 我们可以先用并查集维护这N个数分别属于哪个集合，每个集合都用一个二项堆来存。 对于每次操作，先查找集合A的最大值w，把w/2插入集合A，然后删除集合A的最大值，集合B也是如此处理。最后合并集合A和B的二项堆。 这个问题就被解决了，时间复杂度大概是O(MlogN)。 Part 2 斐波那契堆 河北省石家庄市第二中学 李煜东 斐波那契堆的发明者 斐波那契堆是由Fredman和Tarjan在1984年发明的。 Tarjan的主要发明： 关于图的连通性的Tarjan算法 伸展树(Splay Tree) 动态树(Link-Cut Tree) 斐波那契堆(Fibonacci Heap) 在此向Tarjan表示崇高的敬意！Orz！！！ 什么是斐波那契堆 斐波那契堆基于堆排序树，但它并不像二叉堆那样是一棵树，而是