Fibonacci 堆 | Codeboy's Blog

形式陈述

结构与接口

作为一种可合并优先队列，Fibonacci 堆用有限的有根树组成森林，每棵树满足父键不大于子键。空堆的根表为空，最小根指针也为空；find-min 与 delete-min 要求堆非空。所有根放在双向循环链表中，并维护最小根指针；节点记录 degree、parent、child 和 mark。insert 添加单节点根，meld 拼接根链表，二者实际 $O(1)$ 。delete-min 删除最小根，把其孩子提升为根，再反复链接同 degree 根，直到根 degree 唯一。

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

势能分析

取

\Phi(H)=t(H)+2m(H),

其中 $t$ 是根数， $m$ 是有 mark 的非根数。设一次 decrease-key 共切断 $c\ge1$ 个节点。首次切断的节点可能没有 mark；其后 $c-1$ 次级联切断都发生在已标记的非根上，逐次清除 mark。停止时至多给一个此前未标记的非根加 mark，因此

\Delta t=c,\qquad \Delta m\le2-c,\qquad \Delta\Phi\le4-c.

这一下降支付与 $c$ 成正比的切断工作；计入实际指针操作时可把势能乘以一个固定常数。未发生切断的调用本来只需常数工作，所以 decrease-key 为摊还 $O(1)$ 。delete-min 的 consolidation 以减少根数支付扫描和链接，最终只剩 $O(\log(n+1))$ 个可能 degree，故为摊还 $O(\log(n+1))$ 。

degree 上界

设节点 $x$ 当前仍保留 $d$ 个孩子，按它们成为 $x$ 的孩子的时间排列为 $y_1,\ldots,y_d$ 。链接 $y_i$ 时，前面 $i-1$ 个仍保留的孩子已经在 $x$ 下，所以当时 $x$ 的 degree 至少为 $i-1$ 。链接只发生在同度根之间，故 $y_i$ 当时的 degree 也至少为 $i-1$ 。此后它一直是非根，最多失去一个孩子而不被切断，因此当前 degree 至少为 $\max(0,i-2)$ 。这里用的是这个下界，不要求各孩子链接时的 degree 按时间递增。

令 $F_0=0,F_1=1$ 。对子树节点数归纳， $y_i$ 的子树至少含 $F_i$ 个节点（ $i=1$ 时至少含它自身），各孩子子树互不相交，于是

|T_x|\ge1+\sum_{i=1}^{d}F_i=F_{d+2}.

单节点情形 $d=0$ 也满足此式。Fibonacci 数随下标指数增长，故 $d=O(\log(n+1))$ ；这才给 consolidation 的度数数组提供对数长度保证。

直觉

Fibonacci 堆把原本每次更新都做的整理延迟到 delete-min：新增根暂不合并，减键只切断已经第二次失去孩子的松弛节点。根数和 mark 数记录了尚未偿还的结构债务；consolidation 与级联切断真正发生时，势能下降支付这批延迟工作。

Fibonacci 堆减键后切下节点并因父节点已标记而继续级联切断 — 减键、标记与级联切断

例子与边界

级联切断例子与边界

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

insert 与 meld 的根表操作本身为最坏常数时间；decrease-key 与 delete-min 的主要保证则是摊还界。单次 delete-min 可处理线性多个根，单次 decrease-key 也可能沿长祖先链级联切断。指针布局和分配成本还会影响实际速度，不能只看渐近表判断工程优势。

完整成本表与删除

在节点分配与局部指针操作按常数成本计算的模型中，make-heap、find-min、insert、meld 的最坏实际成本为 $O(1)$ ，decrease-key 为摊还 $O(1)$ ，delete-min 与任意 delete 均为摊还 $O(\log(n+1))$ 。删除指定节点可先把它降到严格小于所有合法键的特殊标记，再执行 delete-min；后一步的对数成本不能省略。若键域不含这样的哨兵，可在内部比较器中另加删除标志，或使用原生切断与删除流程，不能拿一个可能与真实键相等的值冒充负无穷。

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

推论与应用

从接口到 Dijkstra 的成本

用邻接表实现非负权图上的 Dijkstra 算法，并为每个活动顶点维护稳定句柄。至多 $n$ 次 extract-min 各花费摊还 $O(\log(n+1))$ ，至多 $m$ 次 decrease-key 各花费摊还 $O(1)$ ，加上插入和扫描出边，得到 $O(m+n\log(n+1))$ 总时间。队列更换为二叉堆时，减键也需要对数时间，才出现两种实现的理论差异。

这个推导依赖本页势能法给出的整段操作成本，不把某次较慢的调用变成快速调用。若改用重复插入距离记录、弹出后忽略旧记录的接口，就不再直接使用这份减键计数；内存占用与弹出次数也必须重新分析。

有根树的最大度为 $O(\log n)$ ，不代表每棵树的高度也为 $O(\log n)$ 。consolidation 数组按度索引，所以需要的是度界；单次级联切断可能很长，必须由 mark 对应的信用支付。这两条证明责任不能互换。

参考资料

Michael L. Fredman、Robert Endre Tarjan，Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms，Journal of the ACM 34(3), 1987，pp. 596–615，§2：基本结构、删除与摊还界。
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，Introduction to Algorithms, 3rd ed., MIT Press, 2009，Chapter 19。
David Karger，Fibonacci Heaps，MIT 6.854，2021，§1.1 的级联势能与按存留孩子链接次序的度数证明。

形式陈述 ​

结构与接口 ​

势能分析 ​

degree 上界 ​

级联切断例子与边界 ​

完整成本表与删除 ​

从接口到 Dijkstra 的成本 ​

反向链接