可并优先队列

接口层 ​

优先队列公理库优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。接口扩展为 make-heap、find-min、insert、meld、decrease-key 和 delete-min。Meld 应避免逐个搬运全部元素；decrease-key 通常接收稳定句柄，否则重复键无法定位对象。

接口不承诺成本。二叉堆最小查询 $O(1)$、插入删除 $O(\log n)$，朴素 meld 为 $\mathrm{\Theta }(n)$；二项堆、Fibonacci 堆与 pairing heap 有不同最坏或摊还表。“decrease-key 为 $O(1)$”必须注明结构和摊还含义。

事件队列合并 ​

两个模拟器各维护事件堆，组件连接后需合并队列。数组堆拼接后线性 heapify 适合偶发合并，却不支持频繁亚线性 meld；树形堆可连接根表，把整理延后到 delete-min。

Meld 后外部句柄仍须有效。复制节点或重新编号会使句柄悬空。重复优先级要把键与对象身份分开，稳定性也不是 ADT 自动提供。

工程边界 ​

只需 push/pop 且缓存局部性重要时，二叉堆常更快。持久化、并发与最坏延迟是额外轴，不能从“可并”推出。

Dijkstra 若用“插入新距离、弹出时忽略旧条目”代替稳定句柄上的 decrease-key，正确性可以保留，但堆大小与操作序列已改变。比较理论界或内存占用时，必须注明采用哪一种接口实现。

操作语义与句柄生命周期 ​

Insert 返回指向逻辑节点的句柄；meld 后句柄仍必须定位同一对象；decrease-key 修改键并恢复堆序；delete 可通过 decrease 到负无穷再 delete-min，前提是键域允许哨兵，否则需要原生删除。重复键时句柄而非键值区分对象。

两个二项堆根阶分别为 $(0,2)$ 与 $(0,1)$。归并后阶 0 两棵连接成阶 1，随后出现两个阶 1 再连接成阶 2；根键较小者成为父。这个过程像二进制加法，根表最终每阶至多一棵，节点数的二进制表示决定树阶集合。

成本来源 ​

二项堆 meld 扫 $O(\log n)$ 个阶；Fibonacci heap 只拼接根链表为摊还 $O(1)$，把同阶合并延迟到 delete-min。势可取“根数加两倍标记节点数”：decrease-key 的级联切割增加根却清除标记，摊还常数；delete-min 的 consolidation 减少大量根，支付扫描。

这些是摊还结论。要求每次 delete-min 最坏对数时需更严格结构；只写“Fibonacci heap 操作更快”会掩盖延迟清理和缓存局部性。

选择边界 ​

Dijkstra 中 decrease-key 多，理论改进可能重要；事件模拟只有 insert/delete-min 时，数组堆连续存储常更快。Pairing heap 代码简单、实测好，但部分 decrease-key 理论界与 Fibonacci heap 不同。接口相同不表示保证表相同。

参考资料

• Michael Fredman, Robert Tarjan, “Fibonacci Heaps and Their Uses,” JACM, 1987.
• Robert Tarjan, Data Structures and Network Algorithms, 1983.
• MIT 6.854, heap notes.