Pairing Heap

表示与基本 Link ​

最小 Pairing Heap 是一棵堆序多叉树：父键不大于任一孩子键。节点通常保存 firstChild、nextSibling，为支持常数实际时间切断还需父指针或前驱兄弟信息；根指针同时给出最小键。

link(x,y) 比较两根，把较大根接为较小根的第一个孩子，实际成本 $O(1)$。因此 find-min、插入单节点和 meld 两棵堆都只需常数实际时间，且不维护度数、秩或标记位。

这种极简性使它成为 自调整结构公理库自调整数据结构Self-adjusting data structure不维护显式平衡证书，而由访问序列持续重排并获得序列敏感摊还界。：树形不在每次更新后保持显式平衡，效率来自后续配对规则与整段操作序列的摊还分析。

Two-pass delete-min ​

删除根后，它的孩子成为一列独立堆。经典 two-pass pairing 执行：

1. 从左到右把相邻孩子两两 link；若剩一个就原样保留。
2. 从右到左把第一遍所得堆依次 link 成一棵树。

第一遍避免把所有孩子单向挂成长链，第二遍让后产生的大树与左侧结果平衡合并。若根有 $d$ 个孩子，本次实际工作为 $\mathrm{\Theta }(d)$；势能下降支付大度根的集中整理，得到 delete-min 摊还 $O(\log n)$。

可追踪例子 ​

根 $1$ 的孩子键依次为 $7,3,9,4,8$。第一遍得到 link(7,3) 的根 $3$、link(9,4) 的根 $4$，以及单独的 $8$。第二遍先 link$(4,8)$ 得根 $4$，再 link$(3,4)$ 得根 $3$；原根删除后，新最小值为 $3$。

若第二遍也从左到右累积，可能反复把越来越大的树接到同一侧。那是另一 pairing strategy，不能无证明地继承经典 two-pass 的分析。

decrease-key 与安全复杂度表 ​

给定稳定句柄，把非根节点 $x$ 的键减小后，若它违反父子堆序，就从兄弟链切下 $x$，再与根 link。实际指针工作可以是 $O(1)$，但势可能显著增加，所以不能据此宣称摊还 $O(1)$。

对经典 two-pass Pairing Heap，一张保守且可复用的表是：insert、find-min、meld 为最坏 $O(1)$，delete-min 为摊还 $O(\log n)$，decrease-key 可安全写成摊还 $O(\log n)$。更精细研究给出 $2^{O(\sqrt{\log \log n})}$ 型次对数上界和相应下界，但依赖准确的结构/操作定义，仍不同于 Fibonacci Heap 的摊还常数。

工程表现不等于理论最优 ​

Pairing Heap 不维护秩和级联标记，节点较小、分支少，许多工作负载中比元数据复杂的堆更快。这是实现与缓存层面的观察，不会把未证明的 decrease-key 界变成定理。

Fibonacci Heap公理库Fibonacci 堆Fibonacci heap以延迟合并和级联切断取得常数摊还插入、合并与减键的可并优先队列。以更复杂的不变量保证 insert、meld、decrease-key 摊还 $O(1)$；二项堆公理库二项堆Binomial heap · 二项式堆以每个度数至多一棵二项树表示键集合，并像二进制进位一样连接同阶树以支持最坏对数时间合并与删除最小值。则按度立即 consolidation，meld 与 delete-min 最坏 $O(\log n)$。三者实现同一可并优先队列公理库可并优先队列Meldable priority queue · Mergeable heap把 meld 与句柄更新纳入优先队列接口，并区分具体堆结构的保证类型。接口，却分别依赖自调整、延迟整理和二进制进位。

任意删除与句柄语义 ​

删除非根节点可先执行 decrease-key 到一个严格小于所有合法键的哨兵，再 delete-min；若键域没有负无穷或最小哨兵，就需要原生切断并把该节点的孩子重新配对。后者的实际与摊还成本必须计入孩子数，不能只按一次根 link 收费。

外部句柄应始终指向同一逻辑节点。Pairing Heap 通常移动节点链接而不交换整份载荷，这一点与某些通过交换键上浮的二项堆实现不同；重复键时尤其不能用键值代替对象身份。

失败边界 ​

切断节点时若没有常数时间找到它在兄弟链中的前驱，decrease-key 的实际成本可能随兄弟数增长。Meld 后旧堆头应失效；重复使用会共享并破坏同一棵树。

不同论文中的 one-pass、multi-pass、auxiliary-list 或 randomized pairing heap 不是同一算法。引用复杂度时必须同时写清 linking schedule、是否允许 decrease-key、保证是最坏还是摊还，以及随机性来自哪里。

参考资料

• Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E. Tarjan, “The Pairing Heap: A New Form of Self-Adjusting Heap,” Algorithmica 1, 1986.
• Seth Pettie, “Towards a Final Analysis of Pairing Heaps,” FOCS, 2005.
• Michael L. Fredman, “On the Efficiency of Pairing Heaps and Related Data Structures,” Journal of the ACM 46(4), 1999.