Fibonacci 堆

Fibonacci 堆把原本每次更新都做的整理延迟到 delete-min：新增根暂不合并，减键只切断已经第二次失去孩子的松弛节点。根数和 mark 数记录了尚未偿还的结构债务；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 会让势能和级联语义同时出错。最小指针在根表重建过程中也必须重新扫描更新。

Fibonacci 堆的常数摊还 decrease-key 依赖势能法公理库势能法Potential method用数据结构状态势能的变化修正实际成本以界定均摊成本。：根数与标记节点数储存延迟合并和级联切割的信用，delete-min 再释放势能支付 consolidation。

从接口到 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以近完全二叉树表示并满足父子堆序的优先队列结构。实现。