可并优先队列

可并优先队列把两批有序竞争者的合并当作一级操作，而不是逐元素重新插入。不同堆结构只是在“何时整理同阶树或恢复秩不变量”上分配成本：立即整理给出直接最坏界，延迟整理则用势能换取便宜 meld 与 decrease-key。

事件队列合并 ​

两个模拟器各维护事件堆，组件连接后需合并队列。数组堆拼接后线性 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；根键较小者成为父。这个过程像二进制加法，根表最终每阶至多一棵，节点数的二进制表示决定树阶集合。

可并堆常把结构整理延迟到 delete-min 或关键切割，因而需要摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。区分单次尖峰与长期操作序列成本。接口支持 meld 不等于 meld、decrease-key 与 delete-min 都有相同保证。

Pairing Heap公理库Pairing HeapPairing heap · 配对堆以一次根连接和两遍兄弟配对实现的自调整多叉堆，代码简洁且工程表现良好，但 decrease-key 的经典理论界需谨慎区分。以多叉堆和配对合并实现 meld、insert 与 delete-min，代码短且常有良好局部性能。它与 Fibonacci 堆共享可并接口，却不共享所有已知摊还界，尤其不能只凭相似的切割操作宣称同样的 decrease-key 理论保证。

成本来源 ​

二项堆 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 不同。接口相同不表示保证表相同。