null path length · 右脊 · meld

可并堆：leftist 与 skew

前两页的堆都住在一个数组里，好处是没有指针、访存连续。这一页换一个提问方式：把两个堆合成一个，要付多少代价。

数组式堆的答案是「与两堆的总元素数同阶」，而指针式结构能把它降到对数级。为这一个操作换掉整套存储布局值不值得，取决于 meld 在负载里占多大比重。

1 · 数组式堆缺的那个操作

两个二叉堆各自是一个合法数组，把它们首尾接起来得到的数组一般不满足堆序：后一段的根落在前一段某个叶子的位置上，与新父亲毫无关系。修复只能重来一遍 Floyd 建堆，扫过全部元素。

定理 1.1 设两个数组式堆的元素数分别为 $n_1$ 与 $n_2$ 。任何只依赖下标算术的 meld 实现，最坏情况下需要 $\Omega(n_1 + n_2)$ 次比较。

证明结果必须是一个长度 $n_1 + n_2$ 的合法堆数组。合法性要求每个元素都不大于它在新数组里的两个孩子，而新数组里的父子配对与原来两个数组里的配对没有交集（除去下标 0 附近的常数个位置）。于是每个元素至少要参与一次新的比较，比较次数不低于 $(n_1 + n_2 - O(1)) / 2$ 。∎

实测把这条界画得很清楚：4096 个 key 分成 16 个堆再依次并成一个，数组重建做了 37499 次比较，leftist heap 只做 154 次，相差 244 倍。

2 · null path length 与右脊上界

指针式堆的思路是让 merge 只碰一条路径，其余子树整棵原样接过去。选定的那条路径是右脊：从根出发一路沿 right 指针走到底。

定义 2.1（null path length） 节点 $x$ 的 $\mathrm{npl}(x)$ 是从 $x$ 出发到某个空位的最短距离，空指针的 $\mathrm{npl}$ 记作 $0$ 。leftist heap 在堆序之外多要求一条：每个节点满足 $\mathrm{npl}(\mathrm{left}) \ge \mathrm{npl}(\mathrm{right})$ 。

这条约束把「短的一侧」逼到右边。

定理 2.2 含 $n$ 个节点的 leftist heap，右脊长度不超过 $\lfloor \log_2 (n+1) \rfloor$ 。

证明若某节点的 $\mathrm{npl}$ 为 $r$ ，则它到任何空位的距离都不小于 $r$ ，于是它的前 $r$ 层是满的，子树至少含 $2^r - 1$ 个节点。根的 $\mathrm{npl}$ 恰等于右脊长度（右脊末端就是最近的空位），代入得 $n \ge 2^r - 1$ ，即 $r \le \log_2(n+1)$ 。∎

merge 的写法随之确定：取两个根中 key 较小的当新根，把新根的右子树与另一棵堆递归 merge，返回后比较两个孩子的 $\mathrm{npl}$ ，必要时交换，最后把新根的 $\mathrm{npl}$ 更新为右孩子的加一。递归只走两条右脊，长度都是对数级。

图 2-1 · 同一批 key 建成的 leftist heap 与 skew heap 并排，红色是右脊，左侧每个节点标出它的 npl。可合并两个堆再逐个弹出最小值，观察两侧形状与比较次数的分化。

3 · 无条件交换换来的摊还界

skew heap 把定义 2.1 整条删掉：不存 $\mathrm{npl}$ 字段，也不比较它，merge 递归返回时无条件交换左右孩子。

代码短了一个字段与一次判断，单次操作的上界随之消失。长右脊确实会出现：8000 个 key 的实测里，skew 的最长右脊达到 23，而同样规模下 leftist 的上界只有 12。

保证换成了摊还形式。Sleator 与 Tarjan 在 1986 年给出的势函数是「重右孩子」的个数（子树较大的那个孩子恰好挂在右边的节点数）：一条长右脊里必然有很多重右孩子，无条件交换把它们全部变轻，释放出的势正好抵掉这次操作的超额代价。 $m$ 次操作的总代价仍是 $O(m \log n)$ 。

4 · merge 作为唯一原语

两种堆都只需要实现一个函数：

insert(root, k) 是 merge(root, 单节点堆)
deleteMin(root) 是 merge(root.left, root.right)
meld(a, b) 就是 merge 本身

数组式堆的三个过程（sift-up、sift-down、Floyd 建堆）在可并堆里合并成一个。正确性证明与不变量维护都只需做一遍，这是可并堆在实现上最实在的好处。

代价是每个节点两根子指针，leftist 还要多存一个整数 $\mathrm{npl}$ 。节点分散在堆内存里，访存不再连续，同规模下的常数明显高于数组式堆。

5 · 两种可并堆的实测账

图 5-1 · 上表是装入并全部弹出时两种堆的比较次数与右脊长度，下方柱状图是把若干个已建好的堆并成一个的 meld 代价。可换元素个数与要并起来的堆数。

装入 8000 个 key 再全部弹出，leftist 合计 152004 次比较，skew 合计 159232 次。

这个结果推翻了本页写作时的预期。skew 少一个字段、少一次判断，原以为比较次数也该更省，实测它多 4.8%。差额几乎全在装入那一半：leftist 51547 次，skew 59640 次，多 15.7%；而弹出那一半 skew 反而少 0.9%（99592 对 100457）。合理的解释是插入的模式特殊——每次都是与一个单节点堆合并，无条件交换会把刚接上的新节点甩到左边，下一次插入面对的右脊反而更长。这个解释未在文献里找到对应的分析，此处只作为观察记录。

选型的分界不在比较次数上，而在「单次操作有没有上界」。实时系统与有延迟预算的场景要 leftist 的最坏界，代码量优先的场合用 skew。

6 · 参考文献

Crane, C. A. (1972). Linear lists and priority queues as balanced binary trees. Technical Report STAN-CS-72-259, Stanford University.
Knuth, D. E. (1973). The Art of Computer Programming, Vol. 3: Sorting and Searching, §5.2.3. Addison-Wesley.
Sleator, D. D., & Tarjan, R. E. (1986). Self-adjusting heaps. SIAM Journal on Computing, 15(1), 52–69.