题目
请实现一个支持 insert、meld、find-min、extract-min、decrease-key 和 delete 的 Fibonacci Heap。解释根链表、父子关系、degree、mark 标记和级联切断如何协作，并用势能函数说明为什么 insert、meld、find-min、decrease-key 可以达到 O(1) 摊销时间，而 extract-min 为 O(log n) 摊销时间。
面试官考察点
- 能否区分实际单次成本与摊销成本，不把 O(1) 摊销说成每次都 O(1)。
- 能否维护循环双向链表、最小根指针、节点句柄和父指针。
- 能否正确实现 decrease-key 的切断、标记和级联切断。
- 能否说明 Fibonacci Heap 的理论优势、工程常数和与 pairing heap、binary heap 的取舍。
参考答案
Fibonacci Heap 是一组满足堆序的树。根节点组成循环双向链表，每个节点保存 parent、child、degree 和 mark。结构允许先延迟合并，extract-min 时再把根链表中的树按 degree 合并。
insert 只需把新节点加入根链表并更新最小值；meld 把两个根链表拼接。decrease-key 若破坏堆序，就把节点从父节点的 child 链表切下并放入根链表；如果父节点已经被切过，再递归级联切断。mark 表示节点是否已经失去一个孩子，用于限制级联损失。
extract-min 将最小根的孩子提升到根链表，删除该根，再按 degree 反复链接同阶树。势能通常定义为根数加上两倍的标记节点数。插入和 meld 增加根数但只支付常数，decrease-key 的级联切断减少标记节点并由势能抵消；extract-min 的实际链接次数被树高限制在 O(log n)。
实现示例
下面的伪代码只展示 decrease-key 的关键路径，节点句柄由调用方保存。
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)实现 extract-min 时要先安全遍历被提升的孩子，再删除最小根。链接同阶根节点时必须更新 parent、child、degree 和 mark，并在最后重新扫描根链表找到新的 min。
常见误区
- 只写出二叉堆式数组实现，却声称支持 Fibonacci Heap 的 O(1) 摊销 decrease-key。
- 切断节点后忘记清空 parent 或 mark，导致下一次级联切断错误。
- 在循环双向链表遍历时边删除边使用失效的 next 指针。
- extract-min 后只比较根节点，不把新提升的孩子纳入根链表和最小值扫描。
- 只比较渐进复杂度，忽略指针跳转、缓存局部性、内存分配和实现复杂度。
复杂度取舍
在 decrease-key 很频繁、需要 meld 且分析模型允许摊销时，Fibonacci Heap 的理论优势明显，经典应用是改进 Prim 或 Dijkstra 的边界分析。实际工程中 pairing heap、rank-pairing heap 或 binary heap 常因更简单、更好的缓存行为而更有竞争力。
Fibonacci Heap 的复杂度依赖节点句柄；如果调用方只能按键查找节点，额外索引会改变设计。多线程环境还需要明确根链表和句柄的所有权，不能把无锁安全性从摊销分析中推导出来。
先验证单节点、重复键、meld 空堆、连续 decrease-key 和删除最后一个节点。再生成随机操作序列，与一个参考优先队列比较最小值和 extract-min 顺序。针对级联切断构造一个节点连续失去两个孩子的测试，确认第一次只标记、第二次才切断。
参考资料
- MIT OpenCourseWare Fibonacci heaps 讲义：势能分析与 decrease-key、extract-min 复杂度。
- Fibonacci Heaps Revisited：级联切断和摊销边界的再分析。
- Fredman 与 Tarjan 的原始论文：Fibonacci Heap 及其网络优化算法应用。
追问
为什么 mark 节点要在势能中计两倍？
级联切断会减少一个标记节点并增加一个根节点。给标记节点两单位势能，可以支付清除标记和加入根链表的成本，使整段级联的摊销代价保持常数。
extract-min 为什么是 O(log n) 摊销？
删除最小根并提升孩子后，链接过程让每个 degree 至多保留一棵树。堆序保证节点的 degree 与子树规模相关，因此最大 degree 是 O(log n)，根链表整理的链接次数也受此限制。
meld 为什么可以 O(1) 摊销？
两个循环根链表可以直接拼接，并比较两个 min 指针。没有立即合并同阶树，代价被留给未来的 extract-min。
什么时候 binary heap 更合适？
当 decrease-key 不频繁、需要数组局部性、节点句柄不方便维护或团队更看重可读性时，binary heap 的 O(log n) 操作和简单实现通常更合适。
如何处理 delete？
常见做法是把节点的键降到负无穷，再执行 extract-min；生产实现必须定义键域、哨兵值和句柄失效规则，避免把正常业务键误当成哨兵。