二项堆与斐波那契堆.

理想王国的数据结构——二项堆与斐波那契堆BinomialHeap&FibonacciHeap广西柳州高级中学王启圣liouzhou_101河北石家庄二中李煜东lydrainbowcat&Part1二项堆广西柳州高级中学王启圣二项堆是神马•在计算机科学中，二项堆（binomialheap）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（mergeableheap）抽象数据类型的一种。二项堆有神马用•堆，就是用来维护一堆关键字的最值，插入一个关键字，以及删除最值。•用一般的二叉堆不就可以了么？二项堆有神马用？二项堆有神马用•假若用二叉堆来启发式合并一堆东西的话时间复杂度就是O(Nlog2N)。•二项堆是可合并堆，时间复杂度可以做到O(NlogN)。•fibonacci堆的思想是基于二项堆的，今晚的主角是fibonacci堆，所以自然要说下二项堆啦~~~二项树我们先定义一下二项树的概念。二项树是一种通过递归定义的有序树，可以由以下定义得到：•度数为0的二项树只包含一个结点•度数为k的二项树有一个根结点，根结点下有k个子女，每个子女分别是度数为0,1,2,…,k-2,k-1的二项树的根。二项树•度数为k的二项树共有2k个结点，高度为k。•在深度d处有Cnd（二项式系数）个结点，n是节点总数。二项堆二项堆是指满足以下性质的二项树的集合：•每棵二项树都满足最小堆性质，即结点关键字大于等于其父结点的关键字•不能有两棵或以上的二项树有相同度数（包括度数为0）以上第一个性质保证了二项树的根结点包含了最小的关键字。第二个性质则说明结点数为N的二项堆最多只有logN+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)。例题•ZOJ2334MonkeyKing•有N个互相独立的数值分别属于N个集合。•有M次操作，每次操作的对象是两个不同的集合A和B，把A和B中的最大值都减少一半，然后合并两个集合，并询问该集合当前最大值。例题Part2斐波那契堆河北省石家庄市第二中学李煜东斐波那契堆的发明者斐波那契堆是由Fredman和Tarjan在1984年发明的。Tarjan的主要发明：关于图的连通性的Tarjan算法伸展树(SplayTree)动态树(Link-CutTree)斐波那契堆(FibonacciHeap)在此向Tarjan表示崇高的敬意！Orz！！！什么是斐波那契堆斐波那契堆基于堆排序树，但它并不像二叉堆那样是一棵树，而是一组最小堆有序树构成的森林。斐波那契堆是一种可合并堆。斐波那契堆中的树是有根、无序的，树根之间用双向循环链表连接起来。因此它的结构类似于二项堆。斐波那契堆的名字来源于对其时间复杂度的分析过程。相比二项堆，斐波那契堆的结构更加灵活。它的主导思想是懒惰化——不得不做的时候再调整堆的结构。这使得斐波那契堆能在O(1)的时间内完成大部分类型的操作。相关数据结构的时间复杂度比较数据结构操作无序链表有序链表二叉堆二项堆斐波那契堆插入InsertO(1)O(N)O(logN)O(logN)O(1)查询最小值GetMinO(N)O(1)O(1)O(logN)O(1)抽取最小值ExtractO(N)O(1)O(logN)O(logN)O(logN)删除DeleteO(1)O(1)O(logN)O(logN)O(logN)减小关键字DecreaseO(1)O(N)O(logN)O(logN)O(1)合并MergeO(1)O(N+M)O(N+M)O(logN)O(1)斐波那契堆的结构堆中各个有序树的树根之间用双向循环链表连接。每颗有序树中兄弟节点之间用双向循环链表连接。每个节点拥有fa，child，last，next四个指针：分别指向父节点、任意一个子节点、左右相邻的兄弟节点。每个节点还记录dat，du，mark三个值：分别表示关键字的值、度数(子节点个数)、剪枝标记。一个指针p，指向所有树根中关键字最小的那个。通过这个指针可以访问该斐波那契堆。斐波那契堆的节点（上图）以及节点间的指针（下图）斐波那契堆支持的基本操作插入一个节点x（Insert）创建一棵仅含有节点x的树，并插入到斐波那契堆的树根链表中更新指针P指向的节点（如果需要）查询最小值（GetMin）直接返回指针P指向的节点的关键字值由于斐波那契堆中的所有树均满足最小堆性质，因此最小值就是所有树根关键字的最小值。合并两个斐波那契堆（Merge/Union）将两个斐波那契堆的树根链表连接起来（连接两个双向循环链表）更新指针P指向的节点（如果需要）合并斐波那契堆中的两棵有序树两棵有序树，根节点分别为x、y。如果x的关键值比y小，把y作为x的子节点，加入到x的子节点的兄弟双向循环链表中，x的度数加一。反之，应该让x成为y的子节点，y的度数加一。抽取最小值（Extract）抽取最小值，就是先查询最小值，然后删除其所在的节点。删除最小节点的步骤：1.建立logN+1个桶，桶的编号为0~logN。2.拆散树根链表，并把除最小节点所在树之外的其它树，放入编号为树根节点度数对应的桶中。3.把以最小节点的的子节点为根的所有子树，按照子树树根度数放入对应的桶中。4.建立一个新的树根链表L，从小到大扫描所有的桶。(1)如果当前桶中仅剩一棵树，将树根连接到L中。(2)否则合并桶顶的两棵有序树。5.扫描新的树根链表L，找到最小节点，并用P指向它。什么是Mark标记当一个节点失去一个孩子节点时，为它打上一个标记，记为Mark。斐波那契堆保证每个节点至多失去一个孩子。根节点的Mark标记永远为false。换句话说，当一个点成为树根时，应当立即清除它的Mark标记。减小关键字的值（Decrease）如果该节点本身就是树根节点，直接减小它的值并更新P指针。如果减小后，其关键字仍然=父节点关键字，什么也不做。否则1.将该节点从其所在的兄弟链表中移除，插入到树根链表中，更新节点键值，更新P指针，更新父节点度数。2.如果其父节点没有被标记，将父节点标记上。3.否则将父节点从所在的兄弟链表中移除，加入到树根链表中，继续考虑其祖父节点是否被标记……4.以此类推，直至遇到根节点、或者未被标记的节点。其它操作删除（Delete）Delete=Decrease+Extract即首先把要删除的节点的关键值减小为负无穷大，然后删除最小节点。修改关键字的值（Change）减小关键字的值=Decrease增大关键字的值=Delete+Insert即首先删除要修改的节点，再重新插入该节点。平摊分析与势能函数算法在某种情况下花销很大，而大多数情况下开销都很小，此时平摊分析更能均衡地考虑算法的效率。分析斐波那契堆的平摊分析方法是势能方法。Costamo表示平摊代价(amortized)，Costact表示实际代价(actual)，Opi表示第i次操作，DS表示数据结构，φ表示数据结构的势能。考虑一个元过程(第i次操作)：Costamo(Opi)=Costact(Opi)+φ(DSi)–φ(DSi-1)那么总的平摊代价为：∑Costamo(Opi)=∑Costact(Opi)+φ(final)–φ(initial)如果φ(final)=φ(initial)，那么平摊代价就是实际代价的上界。选取一个合适的势能函数φ即可。斐波那契堆的时间复杂度分析插入、查询最小值、合并两个斐波那契堆、合并堆中两个有序树的实际代价和平摊代价均为为O(1)。定义φ(DS)=k*根节点数+2*带标记节点数（常数k不妨设为1）。抽取最小节点：实际代价为遍历根节点和遍历桶的代价，O(根节点数)+O(logN)?合并后树根的度数各不相同，因此合并后最多有logN个树根，所以势能函数的改变为Δφ(DS)=logN–根节点数。平摊代价为：(根节点数+logN)+(logN–根节点数)=O(logN)减小键值：要减小键值的节点变为根、最终有某个未标记的节点被标记，实际代价O(1)，势能变化1+2=3。如果引起多次剪枝，每次有一个点变为根并失去标记，一次的平摊代价=实际代价+势能变化=1+1-2=0。即：多次剪枝的指针操作代价被势能函数平摊，总代价O(1)！关键：证明所有节点度数=logN按照加入顺序考虑节点x的所有孩子。引理：第i个成为x的孩子的节点度数至少为i-2。设该点为y，成为x的孩子之前，y至少有i-1个孩子。因为只有当x和y的度数相等时，才会合并x,y两棵有序树。此后y最多再失去一个孩子(被mark标记)。因此y的度数至少为i-2。令Sk表示度数为k的节点后代的最小数目。S0=1，S1=2，Sk=∑Si(0=i=k-2)。解这个递归式可以得到：Sk=Fibonacci[k+2]。我们知道斐波那契数列是指数级增长的，相邻两项比值无限趋近于黄金分割比1.618。也就是后代节点总数是节点度数的指数。而堆中至多有N个节点，因此度数=logN。再探ZOJ2334MonkeyKing尝试用斐波那契堆解决该问题。由于要维护许多斐波那契堆，因此需要借助并查集维护各个斐波那契堆的P指针。合并两个斐波那契堆时，同时应当在并查集中合并两个P指针所在的集合。在并查集中寻找祖先就是寻找一个节点所在的堆的P指针。用上面提到的结构来维护斐波那契堆。这是最优策略吗？考虑优化仔细分析可以发现，此题有Merge、Change（Extract+Insert），即合并斐波那契堆、修改最大节点的值（本题为大根堆）。没有Decrease操作，因此不需要从树中删除节点。fa、mark域可以省去，兄弟双向循环链表完全没用。结构优化：只保留树根双向循环链表的last和next指针。去掉child指针、把兄弟双向循环链表改为类似于图论中存储边的单向链表，只需要head、next两种指针。合并两棵有序树时直接插入到表头head处。代码实现中，结构体里只保留dat、du两个值，树根指针用last、next数组，其它节点指针用head、next数组。速度提升约一倍左右。斐波那契堆优化的Dijkstra算法BZOJ3