6.1 二叉堆与优先队列

普通队列按照到达顺序取出数据；优先队列则要在当前所有项目中取出键值最小（或最大）的一项。二叉堆不会把所有项目完全排好序，而是只维护足够的结构，使最小项容易取得，并让更新后的修复局限在一条路径上。本节采用课程讲义中的最小堆和从 1 开始编号的数组。

分析每个操作时，我们都分别检查两个不变量：树形是否仍然完全，父子之间是否仍满足堆序。“形状—次序”的分工正是后面所有时间界的来源。

动机

Prim 和 Dijkstra 等算法会反复选择当前代价最小的候选项。若使用未排序容器，加入新项可以很快，但每次寻找最小项都可能扫描整个容器；若始终保持完全排序，最小项容易定位，插入时却可能搬动大量数据。堆采用折中方案：它不保存完整的排序关系，只保证根是最小项，并允许一次更新沿树的竖直路径修复。

优先队列是抽象数据类型；二叉堆只是它的一种实现。实际项目可以是 (暂定距离, 顶点)，由键值决定优先级，payload 随项目一起返回。调用者只应依赖“返回最小键值”这一接口约定，不应把内部堆数组当作已经排好序的列表。

定义

定义

最小优先队列

最小优先队列的核心操作是：insert(x) 加入键值为 x 的项目；find_min() 读取一个最小键值项目；delete_min() 删除并返回一个最小键值项目。抽象定义规定行为，但不指定存储方式。

定义

完全二叉树

如果一棵二叉树除最后一层以外每层都满，而最后一层从左到右连续填入、没有空位，就称为完全二叉树。这只是形状条件，与节点中的键值无关。

本节沿用第 4 章按节点数定义树高的约定：h 是最长根到叶路径所含的节点数，所以空树高度为 0，单节点树高度为 1。深度仍按从根开始经过的边数计算，因此根的深度为零。对于含 n>0 个节点的完全二叉树，h = floor(log_2 n) + 1；等价地，2^{h-1} ≤ n ≤ 2^h - 1。根与叶之间的修复路径最多经过 h - 1 = floor(log_2 n) 条竖直边，因此一次 sift-up 或 sift-down 仍为 O(log n)。

定义

最小堆序

如果每个非根节点的键值都大于或等于父节点，树就满足最小堆序。换句话说，每个父节点都不大于它的子节点。同时具备完全二叉树形状和最小堆序的树称为二叉最小堆。

堆序只是偏序，不是完整排序。兄弟节点之间没有大小约束，左子树中的键值也不一定小于右子树中的键值。允许出现相同键值；除非另设 tie-breaker，堆也不保证相同优先级的项目按到达顺序离开。

定义

从 1 开始的数组表示

按层次把完全二叉树存入 A[1..n]。对于下标 i，

$$\operatorname{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor, \qquad \operatorname{left}(i)=2i, \qquad \operatorname{right}(i)=2i+1.$$

父下标公式只适用于 i>1；子下标不超过 n 时才表示真实节点。内部节点恰好是下标 1 到 floor(n/2)，其余节点全是叶节点。

完全形状使这些公式成立：在 A[n+1] 加入项目就是占据下一个合法位置，删除 A[n] 就是移除最后一个合法位置。判断叶节点只需检查 2i>n。即使数组容量大于 n，当前大小之外的单元也不属于堆，不能参加比较。

定理 / 命题

定理

根最小不变量与 find_min

在非空最小堆中，根 A[1] 保存全局最小键值。因此完成非空检查后，find_min 的时间是 O(1)。

定理

单路径修复界

用 sift-up 修复插入、用 sift-down 修复 delete-min，在含 n 项的二叉堆中，二者的最坏时间都是 O(log n)，并且都能恢复完全形状与最小堆序。

定理

Bottom-up build_heap

先把 n 个键值按完全树顺序放入数组，再依次对下标 floor(n/2), floor(n/2)-1, ..., 1 执行 sift_down，最终数组是最小堆，总的最坏时间为 O(n)。

最后一个结论不能通过“n/2 次操作乘整棵树的最大向下边数”来分析。绝大多数起点靠近叶层，不可能走完 h - 1 = floor(log_2 n) 条边；应当按照每个节点自己的最大向下边数收费。

证明思路

任取节点 v。从根到 v 的唯一路径上，键值单调不减，因此根键值不大于 v。由于 v 任意，根就是全局最小；直接读取 A[1] 不随 n 增长，所以 find_min 为常数时间。这个证明并没有断言“第二小”固定出现在某个数组位置。

插入与 sift-up

先在 n+1 建立空位，完全形状因而保持不变。如果 x 小于空位的父键值，就把父键值移到空位，再把空位移到原父位置；直到父键值不大于 x，或者空位已经到根，才写入 x。

INSERT(A, n, x):
    n := n + 1
    i := n
    while i > 1 and A[floor(i / 2)] > x:
        A[i] := A[floor(i / 2)]
        i := floor(i / 2)
    A[i] := x
    return n

每轮开始时，除空位相连的边以外，其余父子关系都仍然正确。把过大的父键移下来，只会把尚未解决的位置上移一条边；循环停止时，最后一条边也符合堆序。若树按节点数计算的高度为 h，空位最多向上经过 h - 1 = floor(log_2 n) 条边。

delete-min 与 sift-down

直接移走根会在完全树的错误位置留下缺口。因此先保存最小值，取出最后一个键值 last，将 n 减一，再把根看成空位。每一步选择两个子节点中较小的一个；若 last 已经不大于这个子键值就停止，否则把较小子键移上来，空位继续向下。

DELETE_MIN(A, n):
    if n = 0: report underflow
    minimum := A[1]
    if n = 1: return (minimum, 0)
    last := A[n]
    n := n - 1
    i := 1
    while 2 * i ≤ n:
        child := 2 * i
        if child + 1 ≤ n and A[child + 1] is smaller than A[child]:
            child := child + 1
        if last ≤ A[child]: break
        A[i] := A[child]
        i := child
    A[i] := last
    return (minimum, n)

必须提升较小的子节点；若提升较大者，它可能立刻位于更小的兄弟节点上方，从而破坏堆序。循环中，空位下方的两棵子树各自仍是堆，其他路径也未改变。空位每轮向下经过一条边，最多经过 h - 1 = floor(log_2 n) 条边，所以最坏时间为 O(log n)。

Bottom-up 建堆

叶节点没有子节点，本身已经满足堆序。由最后一个内部节点开始倒序处理：

BUILD_HEAP(A, n):
    for i := floor(n / 2) downto 1:
        SIFT_DOWN(A, n, i)

处理 i 时，两个子树的下标更大，已经先成为堆；SIFT_DOWN 只需要修复以 i 为根的子树。对下标做反向归纳，最后下标 1 的整棵树就是堆。

为分析运行时间，令 d 表示从某节点向下到叶节点最多经过的边数，叶节点的 d=0。这个节点最多下降 d 条边，而最大向下边数为 d 的节点只有 O(n/2^{d+1}) 个。因此总工作量为

$$O\!\left(n\sum_{d\ge0}\frac{d}{2^{d+1}}\right)=O(n),$$

因为按向下边数加权的级数收敛到常数（等价地，sum d/2^d = 2）。逐项插入同样可以建堆，并且任何时刻都保持有效堆，适合数据在线到达；但它的最坏总时间为 O(n log n)。Bottom-up 方法在所有键值已到齐时，利用大量节点紧邻叶层这一结构事实得到线性界。

从操作到优先队列契约

空堆上的 find_min、delete_min 必须报告 underflow。固定容量数组满时，需要报错或扩容；这是存储策略，不改变 sift 的结构界。最坏界也不依赖随机输入：新的全局最小值确实可能从最后一个叶节点一路上浮到根，而很大的 last 也可能从根下沉到底层。

例题详解

例题

读取数组关系

对于 A = [4, 9, 7, 15, 12, 11, 10]，下标 3 保存 7；其父节点在下标 1，子节点在下标 6,7，键值分别是 11,10。下标 4 的左子下标为 8>n，所以它是叶节点。该数组是最小堆，但没有整体排序，因为 9>7。

例题

讲义跟踪：插入 14

从 [13, 21, 16, 24, 31, 19, 68, 65, 26, 32] 开始，在下标 11 建立空位。下标 5 的父键值 31>14，把 31 移下来；空位到下标 5 后，下标 2 的 21>14，再把 21 移下来。到下标 2 时，父键值 13≤14，因此停止并写入 14。

最终数组为 [13, 14, 16, 24, 21, 19, 68, 65, 26, 32, 31]，只改动了下标 11,5,2。

例题

讲义跟踪：删除最小值

从 [13, 14, 16, 19, 21, 24, 68, 65, 40, 32, 31] 开始。保存 13，取出最后键值 31。根的子键为 14,16，先提升 14；下一层为 19,21，提升 19；再下一层为 65,40，而 31≤40，所以把 31 写入空位。

返回值是 13，剩余堆为 [14, 19, 16, 31, 21, 24, 68, 65, 40, 32]。

例题

讲义跟踪：bottom-up build_heap

讲义例子先放入 [15, 8, 4, 3, 1, 7, 11, 10, 2, 9, 6, 5, 12, 14, 13]。叶下标 8..15 无需处理。完成下标 7,6,5,4 后得到 [15, 8, 4, 2, 1, 5, 11, 10, 3, 9, 6, 7, 12, 14, 13]；完成 3,2 后得到 [15, 1, 4, 2, 6, 5, 11, 10, 3, 9, 8, 7, 12, 14, 13]；最后处理根，得到 [1, 2, 4, 3, 6, 5, 11, 10, 15, 9, 8, 7, 12, 14, 13]。

根开始 sift-down 时，左右子树已经分别成堆，这正是倒序处理所维护的核心不变量。

操作成本总结

操作成本可以直接由结构读出：find_min 是 O(1)；insert 和 delete_min 各修复一条路径，最坏为 O(log n)；bottom-up build_heap 按向下边数上限加权后为 O(n)；数组每个项目占一个位置，空间为 O(n)。

常见错误

• 把堆数组当作排序结果。 堆序只约束祖先与后代，不比较任意相邻项或兄弟节点。
• 混用从零开始的公式。 本节从 1 开始，所以父为 floor(i/2)、左子为 2i、右子为 2i+1。
• 追加后不做 sift-up。 追加只保持完全形状，新项目仍可能小于父节点。
• 删除根后没有先移除最后位置。 应用最后键值填补根空位并先减小 n，才能保持完全形状。
• sift-down 时提升较大的子节点。 最小堆必须提升较小者，才能让新父节点同时不大于两个子节点。
• 把 build_heap 中每次 sift_down 调用都按 log n 收费。 大多数内部节点最多只能下降一两条边，紧确总界为 O(n)。
• 忽略空堆。 n=0 时不存在合法根，读取或删除前必须检查。

总结

二叉堆把完全二叉树形状和堆序结合起来。完全形状带来对数高度和紧凑的层序数组；最小堆序把全局最小值固定在根。插入在最后位置建立空位并向上修复；delete-min 移走根、用最后键值建立根空位，再沿较小子节点向下修复。两者都只走一条路径。Bottom-up build_heap 从最后一个内部节点倒序开始，因为向下边数上限较大的节点数按几何速度减少，所以总时间为线性。这些性质使堆成为高效的最小优先队列实现。

练习

思考检查

一个大小为 14、从 1 开始编号的堆中，下标 11 的父下标是什么？下标 7 有哪些有效子下标？

套用下标公式后，把每个候选子下标与 n 比较。

思考检查

从 [3, 8, 5, 12, 10, 9] 插入 4。修复向哪个方向移动？最终数组是什么？

先把新项目追加到下一个合法位置，再只与祖先比较。

思考检查

delete-min 的 sift-down 为什么必须提升两个子节点中较小的一个？

说明提升以后，新父节点与两个子节点应满足的关系。

思考检查

即使一次 sift_down 可以用 O(log n)，为什么 bottom-up build_heap 的总时间仍是 O(n)？

按照起点的向下边数上限 d 给节点分组计费。

答案与解答

解答 · 1. 数组关系

下标 11 的父为 floor(11/2)=5。下标 7 的候选子下标是 14,15；堆大小为 14，所以只有 14 有效。

解答 · 2. 插入跟踪

把 4 放到新下标 7。父下标 3 的键值为 5，所以把 5 移下来，空位上移到 3。新的父下标 1 的键值为 3；因为 3≤4，停止。这是 sift-up，最终数组为 [3, 8, 4, 12, 10, 9, 5]。

解答 · 3. 较小子节点

设子键值 a≤b。提升 a 后，新父键值不大于兄弟 b，两条父子边都合法；若 a 严格小于 b 时提升 b，就会立刻使 b 位于 a 上方，违反最小堆序。

解答 · 4. 线性建堆

若 d 是从某节点向下到叶节点最多经过的边数，该节点最多下降 d 条边，而最大向下 边数为 d 的节点只有 O(n/2^{d + 1}) 个。总费用为 O(n sum d/2^{d + 1})=O(n)， 因为该级数为常数。宽松的 O(n log n) 估算错误地把每个内部节点都看成可以经过整棵树 的最大向下边数。