斐波那契堆

斐波那契堆(Fibonacci Heap)

F堆可以认为是“松散”版的二项堆，其也是基于“链表+树”的。F堆上的树无需是二项树，其仅松散的要求链表上的树根出度唯一(仅要求某些运算结构维护该性质)。并且注意到F堆使用“双向循环链表”的物理结构表示链表与树，这种链表不承载序信息，故F堆的链表与树都是无序的。相比二项堆用“孩子兄弟法”表示树，F堆在用“双向循环链表”表示树时，需把所有子节点都指向父节点，而父节点只需一个指向其任意子节点的指针。最后明确“双向循环链表”只有单节点时，该节点的左右指针都指向其自身。F堆用最小节点指针\(min\)实现二项堆的链表表头指针\(head\)的作用。

F堆的运算与二项堆相同，其除\(pop\)与\(delete\)的代价为\(O(lgn)\)，其他运算的代价为\(O(1)\)。所以F堆的理论代价非常的优秀，但由于其实际代价中隐含着“大系数”，故程序语言中的优先队列不用F堆，F堆只适用于需要大量执行其\(O(1)\)运算的场景(如MST/Dijkstra)，所以通常认为F堆只是一个理论上更高效的结构。

为在之后分析时间复杂度，定义\(D(n)\)为任意\(n\)节点F堆的所有节点的出度上界值，\(t(H)\)为F堆\(H\)的链表节点数。根链表节点出度唯一性被满足时\(t(H) \leq D(n(H)) + 1\)，因为该条件下出度取值最坏情况为\([0,1,…,D(n(H))]\)，故链表节点数目的最坏情况为\(D(n(H)) + 1\)。给出F堆几种代价为\(O(1)\)的简单运算的具体实现：

\(push\)：将关键字(节点)插入根链表任意位置，最后更新\(min\)即可；

\(union\)：按任意次序合并两个链表，最后更新\(min\)即可；

\(minimum\)：直接返回\(min\)指针即可；

出堆运算

1) 通过\(min\)找到最小节点将其移出根链表，但把其全部子节点任意的合并到根链表，该步骤类似于二项堆的出堆运算。最后把\(min\)指向任意其他根链表节点(\(min\)的性质会在最后被恢复)；

2) 循环的合并根链表出度相等的树根，直到根链表所有树根出度唯一。循环开始前定义临时Map为\(A[i] = N\)，其中\(i\)为出度，\(N\)为根链表中当前“已检查到”的出度为\(i\)的树根。然后执行嵌套循环如下，循环结束后所有树根出度唯一：

2.1) 外层循环为遍历根链表。每轮循环后已遍历过的树根(包括合并后的新树根)的出度是唯一的；

2.2) 内层循环为合并相同出度的已遍历过的树根。其具体流程为先得出当前树根的出度\(x\)，然后检查\(A[x]\)中是否有节点，如果没有则此时已遍历过的树根的出度都是唯一的，最后更新\(A[x]\)并退出内层循环。否则将两个树根合并为新树根，删除\(A[x]\)的记录，然后继续循环的检查\(A[x+1]\)中是否有节点……

注意到步骤(1)结束后，新链表有至多\(O(t(H)+D(n))\)个节点，步骤(2)至多有\(O(t(H)+D(n))\)次合并，无论外循环如何，内层循环有总次数上界\(O(t(H)+D(n))\)，这是个实际代价上界。循环结束后根链表节点出度无重复，结合上文公式可进一步得上界\(O(2D(n)+1)=O(D(n))\)。

减值运算

减值是把\(H\)指定节点的关键字更新为更小值的运算，利用减值运算可进一步构造与二项堆删除运算逻辑相同的F堆删除运算。首先为节点引入\(mark\)布尔变量，当节点上次成为子节点后失去过孩子则\(mark\)为真，否则\(mark\)都为假，节点初始化时\(mark\)为假。下面讨论减值运算\(decrease(node,key)\)：

1) 若\(node.key < key\)则引发异常，否则设定\(node.key=key\)；

2) 若\(key < parent.key \)，则\(parent\)违反小根堆性质。需把\(node\)子树从\(parent\)“切割”并加入根链表，这样两个树的小根堆性质得以满足。然后维护新的\(node\)树的\(parent\)为空\(mark\)为假，\(parent\)在该步骤仅令其出度减1；

3) 若\(parent\)为根节点则仅需维护出度等变量并退出。否则若\(parent.mark\)为假则将其标记为真，然后维护其他变量并退出。若\(parent.mark\)为真，则需对\(parent\)执行“切割”，并继续递归的对\(parent.parent\)执行步骤(3);

设\(m(H)\)为\(H\)中\(mark\)为真的节点总数，势能\(\Phi(H) = t(H) + 2m(H) \)，\(c\)为上述运算的“切割”次数。则实际代价为\(O(c)\)，运算后链表节点数为\(t(H) + c\)，\(mark\)节点数为\(m(H)-c+O(1)\)。故运算前后势差为\(-c+O(1) \)，摊还代价为\(O(c)-c\)。为势能配正常数\(\Phi’ = A\Phi + B\)，其同样满足\(\Phi'(H_0) = 0\)与\(\Phi’ \geq 0\)，新的摊还代价为\(O(c)-Ac\)。如果选定的\(A\)能大过实际代价中的隐藏常数，则摊还代价\(O(c)-Ac\)可合并为\(-O(c)\)，又由于每次该运算的摊还代价不能小于实际代价，故\(-O(c)\)不能取到这个负号，所以摊还代价为\(O(1)\)。

论证\(D(n) = O(lgn)\)

考虑证明\(D(n) \leq log_{\phi} n\)来证明原命题，其中\(\phi = \frac{1+\sqrt{5}}{2}\)是黄金分割比。该证明的过程蕴涵了“斐波那契堆”这个名字的来历。另外注意本文中的斐波那契数列\(F\)，规定其首元素下标为0，并且\(F_0=0\)。

引理1：设\(x\)为任意F堆的任意节点，\(k\)为\(x\)的出度。在任意运算结束后，将\(x\)的所有下一代节点按被“链入”\(x\)的次序排序为\(y_1,…,y_k\)。那么不等式关系\(y_1.degree \geq 0\)与\(y_i.degree \geq i -2 \)成立。

仅考虑仅在出堆时发生的“链入”，对\(y_i\)(\(i>1\))因为\(y_1,…y_{i-1}\)仅在之前被链入，且链入在两树出度相等时发生，故\(y_i.degree = i-1\)。

若合并考虑\(x\)的下一代发生过“切割”，则\(y_i.degree \geq i-1\)。

再进一步合并考虑\(y_i\)在成为\(x\)的下一代后\(y_i\)的下一代发生过“切割”的情况，根据“减值运算”步骤，\(y_i\)在被“链入”\(x\)作为\(x\)的子节点的前提下，\(y_i\)只有一次子节点被“切割”的机会。综上得出\(y_i.degree \geq i-2\)。

引理2：对任意整数\(k \geq 0\)，斐波那契数列\(F\)满足\(F_{k+2} = 1 + \sum_{i=0}^k F_i\)。

该结论可通过数学归纳法证明，其可被看作是斐波那契数的另一种定义。

\(k=0\)时\(F_2 = 1 + F_0 = 1 + 0\)，故原式成立。

\(F_{k+2} = F_{k} + F_{k+1} = F_{k} + (1+\sum_{i=0}^{k-1} F_i) = 1+\sum_{i=0}^{k} F_i\)，

上式说明若\(k+1\)时原式成立，那么在\(k+2\)时原式也必然成立。至此通过数学归纳法证明了原命题。

引理3：对任意整数\(k \geq 0\)，斐波那契数列\(F\)满足\(F_{k+2} \geq \phi^k\)。

从\(F_2 \geq \phi^0, F_3 \geq \phi^1\)数学归纳，因为\(F_{k+2} = F_{k+1} + F_k\)，故\(F_{k+2} \geq \phi^{k-1} + \phi^{k-2}=\phi^{k-2}(\phi+1) \)，

根据黄金分割比的定义\(\phi\)为\(x^2 = x+1\)的解，故\(\phi^{k-2}(\phi+1)=\phi^k \)，综上有\(F_{k+2} \geq \phi^k \)。

引理4：设\(x\)为任意F堆的任意节点，\(k\)为\(x\)的出度，\(size(x)\)为\(x\)子树的节点总数。则\(size(x) \geq F_{k+2} \geq \phi^k\)。

设\(s_k\)为任意F堆任意出度为\(k\)的节点的最小可能\(size\)(\(s_0=1,s_1=2…\))，\(s_k\)显然严格单调递增。

然后根据引理1有\(s_k \geq 1+1+\sum_{i=2}^k s_{y_{i}.degree} \geq 2+\sum_{i=2}^k s_{i-2}\)。

然后用数学归纳法证明\(s_k \geq F_{k+2}\)，\(k\in \{0,1\}\)时原命题成立，

归纳步\(s_k \geq 2+\sum_{i=2}^k s_{i-2} \geq 2+\sum_{i=2}^k F_i = 1+\sum_{i=0}^k F_i = F_{k+2} \)，结合其他引理原命题得证。

最后利用上述引理证明任意n节点F堆\(H\)所有节点的出度上界为\(O(lgn)\)。设\(x\)为\(H\)的任意节点，则\(n \geq size(x)\)。然后设\(x\)的出度为\(k\)，利用引理4有\(n \geq size(x) \geq  \phi^k\)，解得\(k \leq log_{\phi}n\)，原命题证毕。

具体实现

实现时需要谨慎处理好斐波那契堆的双向循环链表的物理结构，具体Python代码如下：