Fibonacci 堆

结构与接口 ​

作为一种可合并优先队列公理库可并优先队列Meldable priority queue · Mergeable heap把 meld 与句柄更新纳入优先队列接口，并区分具体堆结构的保证类型。，Fibonacci 堆用一组满足父键不大于子键的有根树表示状态。所有根放在双向循环链表中，并维护最小根指针；节点记录 degree、parent、child 和 mark。insert 添加单节点根，meld 拼接根链表，二者实际 $O(1)$。delete-min 删除最小根，把其孩子提升为根，再反复链接同 degree 根，直到根 degree 唯一。

decrease-key$(x,k)$ 若破坏父子堆序，就把 $x$ 切到根表；若其父是非根且此前已失去过孩子，继续级联切断，否则只给父加 mark。mark 表示“成为非根后是否已失去一个孩子”，不是访问标记。

势能分析 ​

取

$$\mathrm{\Phi }(H)=t(H)+2m(H),$$

其中 $t$ 是根数，$m$ 是有 mark 的非根数。一次切断使根数增一，却清除一个 mark；级联切断的实际长度被势能下降支付，所以 decrease-key 摊还 $O(1)$。delete-min 的 consolidation 以减少根数支付链接，最后只剩 $O(\log n)$ 个可能 degree，故摊还 $O(\log n)$。

degree 上界 ​

节点每增加一个孩子，已有孩子按被链接时的 degree 递增；每个非根最多失去一个孩子而不被切断。由此 degree 为 $d$ 的节点子树大小至少为 Fibonacci 数 $F_{d+2}$，所以 $d=O(\log n)$。没有这一步，consolidation 扫描表大小就没有对数保证。

级联切断例子与边界 ​

设非根节点 $y$ 已因一个孩子被切而 marked。再次降低其另一孩子 $x$ 的键，使 $x$ 小于 $y$：先切 $x$，再因 $y$ 已 marked 切 $y$；若 $y$ 的父也 marked，链继续。这把长期积累的结构松弛一次释放。

所有界都是摊还界；单次 delete-min 可处理许多根。复杂指针和缓存局部性使二叉堆在只需 push/pop 的程序中常更快。Dijkstra 的理论改善依赖大量有效 decrease-key，不能只看渐近表就断言工程优势。

完整成本表与删除 ​

make-heap、find-min、insert、meld 的最坏实际成本为 $O(1)$；decrease-key 和 delete 的 $O(1)$ 是摊还（delete 通常先降为 $-\mathrm{\infty }$ 再 delete-min），delete-min 为 $O(\log n)$ 摊还。若键域没有合法 $-\mathrm{\infty }$，删除应提供句柄并直接切到根后执行删除流程，不能塞入会与真实键碰撞的哨兵。

Consolidation 使用按 degree 索引的临时数组，数组长度来自 degree bound。链接同度根时较小键成为父，另一根失去根身份并清 mark；遗漏清 mark 会让势能和级联语义同时出错。最小指针在根表重建过程中也必须重新扫描更新。

从接口到 Dijkstra 的成本 ​

若一轮 delete-min 前有 $t$ 棵根树，它最多执行 $t-1$ 次链接；链接使根数下降 1，而每次真正级联切断会增加根数、同时清除一个 mark。势能的下降正好支付此前由 decrease-key 延迟的整理工作，所以单次 delete-min 虽可能扫描许多根，摊还仍为 $O(\log n)$。

代入邻接表 Dijkstra：$n$ 次 extract-min 各摊还 $O(\log n)$，至多 $m$ 次 decrease-key 各摊还 $O(1)$，得到 $O(m+n\log n)$。这是理论模型中的摊还界；指针密集布局、缓存不友好和较大常数意味着它不自动优于二叉堆公理库二叉堆Binary heap以近完全二叉树表示并满足父子堆序的优先队列结构。实现。

参考资料

• Michael Fredman, Robert Tarjan, Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms, JACM, 1987.
• Cormen et al., Introduction to Algorithms, 4th ed., Ch. 19.