堆

2026 大纲 四（四）3 堆及其应用 —— "堆怎么用"在本篇，"堆怎么排序"在《堆排序》（七（八））。

堆 $=$ 完全二叉树 $+$ 堆序性

定义只有两句：形状上必须是完全二叉树；值上双亲必须优于孩子——大根堆要求 $k_i\ge k_{2i}$ 且 $k_i\ge k_{2i+1}$，小根堆反号，$1\le i\le \lfloor n/2\rfloor$（只需查分支结点）。

    大根堆                  小根堆
      9                       1
     / \                     / \
    7   8                   3   2
   / \ / \                 / \ / \
  4  6 5  3               7  4 8  6

根恒为最值，证明一句话：由堆序性，根 $\ge$ 它的两个孩子，两个孩子又各自 $\ge$ 自己的孩子；沿任意一条从根出发的路径传递下去，根 $\ge$ 路径上每一个结点；而任一结点都在某条这样的路径上。

但请立刻注意反面：堆只保证双亲优于孩子，同层之间、左右子树之间全无约束。 上面那个大根堆里 $7<8$（同层）、$4<6$（同层）、$6>5$（跨子树）全都合法。

所以堆是"局部有序、整体无序"的：取最值 $O(1)$，但查找任意元素是 $O(n)$——堆序性不提供任何"该往左还是往右"的指导。这条能力边界是堆与二叉排序树的根本分野，也是判断题最爱设的坑。

不过"整体无序"里还是能挤出两条确定的结论：

• 大根堆的次大值一定是根的孩子之一。 反证：设次大值 $S$ 不是根的孩子，则它的双亲 $P$ 既不是根也不是 $S$。由堆序性 $P\ge S$；又由 $S$ 是次大值、除根外无人比它大，得 $P\le S$。故 $P=S$，矛盾。
• 大根堆的最小值一定在叶结点中（分支结点必 $\ge$ 自己的孩子），但不一定是最后一个元素。

为什么形状上非要是完全二叉树

完全二叉树的层序编号连续无空洞，可以按编号直接放进数组，双亲与孩子的下标用公式算出来，一个指针都不用存：

$$\text{1-base：双亲 }\lfloor i/2\rfloor ,\text{孩子 }2i\text{ 与 }2i+1;\text{0-base：双亲 }\lfloor (i-1)/2\rfloor ,\text{孩子 }2i+1\text{ 与 }2i+2$$

若允许任意形态，就必须回到二叉链表，$O(1)$ 定位孩子的能力立刻丧失，所有下标公式全部失效。

换个角度看还有第二重收益：完全二叉树是"给定结点数下高度最小"的形态，树高恒为 $\lceil {\log }_2(n+1)\rceil$，这保证了上浮 / 下沉的路径长度是 $O(\log n)$。形态限制既换来存储上的便利，也换来操作上的复杂度保证。

由此还得到两个直接可用的下标事实（1-base）：最后一个分支结点是 $\lfloor n/2\rfloor$，编号 $\lfloor n/2\rfloor +1\sim n$ 全是叶子。建堆的起点就是从这儿来的。

做题第一步永远是看清题面用哪套下标约定，否则双亲孩子会整体错一格，后面全盘皆错。换算不用背：0-base 的 $i$ 换成 $i+1$ 代进 1-base 公式再减 1 即可（左孩子 $2(i+1)-1=2i+1$ ✓）。

只有两个动作：下沉与上浮

下沉（Sift Down）：某结点比孩子劣，就与较优的那个孩子交换，再在新位置继续下沉。上浮（Sift Up）：某结点比双亲优，就往上走。

判据只有一句：比双亲优就上浮，比孩子劣就下沉。 插入 → 上浮；删堆顶 → 下沉；建堆 → 下沉；删任意元素 → 两个都试。

// 大根堆下沉：把 A[i] 沉到合适位置，堆规模为 n（A[1..n]）
// 前提：以 i 的左右孩子为根的两棵子树本身已经是堆
void SiftDown(int A[], int i, int n) {
    int temp = A[i];                     // 暂存，避免每层做完整交换
    for (int k = 2 * i; k <= n; k *= 2) {// k 指向左孩子，每层翻倍下移
        if (k < n && A[k] < A[k + 1])
            k++;                         // k < n 保证右孩子存在；取较大的孩子
        if (temp >= A[k])
            break;                       // 已满足堆序，停止
        A[i] = A[k];                     // 较大的孩子上移一层
        i = k;
    }
    A[i] = temp;                         // 循环结束后 i 就是最终位置
}

// 大根堆上浮：把 A[i] 沿双亲方向浮到合适位置
void SiftUp(int A[], int i) {
    int temp = A[i];
    while (i > 1 && temp > A[i / 2]) {   // i > 1 保证还没到根
        A[i] = A[i / 2];                 // 双亲下移一层
        i = i / 2;
    }
    A[i] = temp;
}

两者都是 $O(\log n)$（路径最长等于树高）。SiftDown 的前提不能忘：两棵子树必须已经是堆。 子树本身乱则一次下沉修不好——这正是建堆必须自底向上的原因。

三处写法细节值得留意：k < n && A[k] < A[k+1] 里 k < n 必须写在前面短路判断右孩子是否存在（$k=n$ 时 $k+1$ 越界）；用 temp 暂存 + 单向搬移，每层只写一次而完整交换要写三次；A[i] = temp 放在循环外，因为最终位置只有循环结束才确定。

教材里这个操作叫"筛选法"——"就像过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来"。

先看一眼

加载可视化中...

上图演示对同一组数据自底向上建最小堆的完整过程（图中下标从 0 开始，所以起点是 $i=3$ 而非本篇正文的 $\lfloor n/2\rfloor$）。(a)(b)(c) 分别是 $i=3,2,1$ 时的局部调整，虚线框圈出的正是"以该结点为根、两棵子树已经是堆"的那棵子树；(d) 处理根结点时发生了连续三次下沉——53 先与 09 交换、再与 17 交换、最后与 23 交换，一路从根沉到了最底层，这正是"一次下沉可能走完整条路径"的典型情形；(e) 是最终的最小堆。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 5.52 自下向上逐步调整为最小堆，p237

建堆：必须自底向上，代价是 $O(n)$

// 大根堆建堆：O(n)
void BuildMaxHeap(int A[], int n) {
    for (int i = n / 2; i >= 1; i--) {   // 从最后一个分支结点倒着往前
        SiftDown(A, i, n);               // 此时 i 的两棵子树已经是堆，前提满足
    }
}

为什么从 $\lfloor n/2\rfloor$ 开始：编号 $>\lfloor n/2\rfloor$ 的全是叶子，单结点天然是堆，下沉是空操作。

为什么必须倒着走：倒序保证轮到结点 $i$ 时，它的孩子 $2i$、$2i+1$（编号都比 $i$ 大）已被处理过，满足"两棵子树已是堆"的前提。正着走会违反前提，建出来的不是堆。

为什么代价是 $O(n)$ 而不是 $O(n\log n)$，这是本节唯一需要推一下的地方。把结点按高度（到最深叶子的距离）分类，在 $n$ 个结点的完全二叉树中高度为 $k$ 的结点至多 $\lceil n/2^{k+1}\rceil$ 个：

高度 $k$	结点数（约）	每个的下沉代价	该层总代价
0（叶子）	$n/2$	0	0
1	$n/4$	$\le 1$	$n/4$
2	$n/8$	$\le 2$	$2n/8$
$h$（根）	1	$\le h$	$h$

$$T(n)\le \sum _{k=0}^h\frac{n}{2^{k+1}}\cdot k=\frac{n}{2}\sum _{k=0}^h\frac{k}{2^k}<\frac{n}{2}\sum _{k=0}^{\mathrm{\infty }}\frac{k}{2^k}$$

这个无穷级数收敛到 2，用错位相减：令 $S=\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\cdots$，则 $2S=1+\frac{2}{2}+\frac{3}{4}+\cdots$，两式相减得 $S=1+\frac{1}{2}+\frac{1}{4}+\cdots =2$。代回 $T(n)<n$。

一句话直觉：自底向上高效，是因为结点数最多的那一层（叶子，占一半）代价为 0，代价最高的那个结点（根）只有一个。反过来"自顶向下逐个插入上浮"是 $O(n\log n)$——结点数最多的最后一层恰恰是上浮路径最长的一层，没法收敛。

对 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] 建大根堆的逐步演示（想跟着手算一遍就展开）

初始：A = [_, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7]

              4(1)
           /        \
        1(2)         3(3)
        /   \       /    \
     2(4)  16(5)  9(6)  10(7)
     /  \    /
  14(8) 8(9) 7(10)

n = 10，最后一个分支结点 i = ⌊10/2⌋ = 5，从 i = 5 倒着处理到 i = 1。

i = 5（值 16）：孩子只有 A[10] = 7。16 > 7，不下沉。
i = 4（值 2）： 孩子是 A[8]=14 和 A[9]=8，较大者 14。
                2 < 14，交换 → A[4]=14, A[8]=2。i=8 已是叶子，停止。
i = 3（值 3）： 孩子是 A[6]=9 和 A[7]=10，较大者 10。
                3 < 10，交换 → A[3]=10, A[7]=3。i=7 是叶子，停止。
i = 2（值 1）： 孩子是 A[4]=14 和 A[5]=16，较大者 16。
                1 < 16，交换 → A[2]=16, A[5]=1。
                继续下沉 i=5：孩子只有 A[10]=7，1 < 7，交换 → A[5]=7, A[10]=1。
i = 1（值 4）： 孩子是 A[2]=16 和 A[3]=10，较大者 16。
                4 < 16，交换 → A[1]=16, A[2]=4。
                继续下沉 i=2：孩子 A[4]=14、A[5]=7，较大者 14，交换 → A[2]=14, A[4]=4。
                继续下沉 i=4：孩子 A[8]=2、A[9]=8，较大者 8，交换 → A[4]=8, A[9]=4。

结果：A = [_, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

逐点自检：$16\ge 14,10$ ✓；$14\ge 8,7$ ✓；$10\ge 9,3$ ✓；$8\ge 2,4$ ✓；$7\ge 1$ ✓

插入、删除与优先级修改

插入放末尾再上浮；删除堆顶把末元素搬到根、规模减 1 再下沉；删除任意位置 $i$ 用末元素填补空位后下沉与上浮各试一次；修改优先级变优则上浮、变劣则下沉。

void HeapInsert(int A[], int *n, int x) {
    (*n)++;              // 堆规模加 1
    A[*n] = x;           // 放到末尾：唯一不破坏完全二叉树形态的位置
    SiftUp(A, *n);       // 向上调整
}

int HeapDeleteTop(int A[], int *n) {
    int top = A[1];        // 保存要返回的最值
    A[1] = A[*n];          // 末元素补到根：保持完全二叉树形态
    (*n)--;
    SiftDown(A, 1, *n);    // 新根只可能劣于孩子，所以是下沉
    return top;
}

void HeapDeleteAt(int A[], int *n, int i) {
    A[i] = A[*n];              // 用末元素填补空位，保持完全二叉树形态
    (*n)--;
    if (i > *n) return;        // 删的就是最后一个，无需调整
    SiftDown(A, i, *n);        // 先试下沉
    SiftUp(A, i);              // 若下沉没动（i 未变），再试上浮
}

两处形态约束是这几行代码的全部理由：完全二叉树只有编号 $n+1$ 那个位置能追加，插入放别处下标公式立刻失效；删堆顶若改成"删根后把两棵子堆合并"，最后一层会出现空洞、不再是完全二叉树，所以必须用末元素填根。

删除任意元素为什么要两个都试：末元素填到位置 $i$ 之后，它既可能比 $i$ 的双亲大（要上浮），也可能比 $i$ 的孩子小（要下沉）。但两者不会同时发生——原来 $A[\text{parent}(i)]\ge$ 原 $A[i]\ge$ 孩子，新值只要不在这个区间内，就只会往一个方向越界。所以"先下沉再上浮"是安全的。

后两个操作都要求先知道下标——堆按值查找是 $O(n)$，实际使用时通常另外维护一张"元素 → 下标"映射表并在交换时同步更新。

插入与删堆顶的手算演示（想跟着算一遍就展开）

插入：在大根堆 $[\mathrm{\_},16,14,10,8,7,9,3,2,4,1]$ 中插入 15。

末尾追加：A[11] = 15，n = 11
15 在下标 11，双亲 ⌊11/2⌋ = 5，A[5] = 7。15 > 7，交换。
15 在下标 5，双亲 ⌊5/2⌋ = 2，A[2] = 14。15 > 14，交换。
15 在下标 2，双亲 1，A[1] = 16。15 < 16，停止。

结果：A = [_, 16, 15, 10, 8, 14, 9, 3, 2, 4, 1, 7]

删除堆顶：对 $[\mathrm{\_},16,15,10,8,14,9,3,2,4,1,7]$（$n=11$）删堆顶。

取出 16；把 A[11] = 7 搬到 A[1]；n 变为 10：
    A = [_, 7, 15, 10, 8, 14, 9, 3, 2, 4, 1]
下沉 i=1：孩子 A[2]=15、A[3]=10，较大者 15。7 < 15，交换 → A[1]=15, A[2]=7
下沉 i=2：孩子 A[4]=8、A[5]=14，较大者 14。7 < 14，交换 → A[2]=14, A[5]=7
下沉 i=5：孩子只有 A[10]=1。7 > 1，停止。

结果：A = [_, 15, 14, 10, 8, 7, 9, 3, 2, 4, 1]，返回 16

数比较次数：两条规则

真题很爱问"调整过程中进行了多少次关键字比较"。手工数的时候按下面两条走，不会错：

上浮：每上一层只比 1 次（当前值与双亲比）。比赢了就交换继续，比输了就停——停下来的那一次也算。

下沉：每下一层看孩子个数——

• 有两个孩子：先"两个孩子互比"选出较优者（1 次），再"父与较优者比"（1 次），合计 2 次；
• 只有一个孩子：不需要兄弟比较，直接父子比，1 次；
• 没有孩子：0 次，结束。

同样，判断"不用交换、就地停下"的那一次比较也要算进去。

举例：小根堆 8, 15, 10, 21, 34, 16, 12 删除堆顶。末元素 12 填到根，下沉——第一层有两个孩子 15 和 10，比 1 次选出 10，再拿 12 与 10 比 1 次（12 > 10，交换），小计 2 次；12 落到原 10 的位置后只剩一个孩子 16，直接比 1 次（12 < 16，停），小计 1 次。合计 3 次。

数错的两个典型来源：一是把"删除堆顶"想成"直接拿走根、左右子树合并"，那样连调整过程都不对；二是漏掉最后那次"发现不用换"的比较。

堆作为优先队列，与 Top-K

优先队列的核心操作是 Insert(x)、GetTop()、ExtractTop()。把几种候选实现摆在一起，堆的位置就清楚了：

实现	插入	取最值	删除最值	问题
无序数组 / 链表	$O(1)$	$O(n)$	$O(n)$	取最值太慢
有序数组 / 链表	$O(n)$	$O(1)$	$O(1)$	插入太慢
平衡二叉搜索树	$O(\log n)$	$O(\log n)$	$O(\log n)$	能做，但常数更大，且提供了用不上的"全序"能力
堆	$O(\log n)$	$O(1)$	$O(\log n)$	—

堆的定位很清楚：它只维护"最值在顶"这一条弱得多的性质，因此比 BST 便宜；而优先队列恰好只需要这一条。 哈夫曼树构造、Dijkstra、Prim、堆排序用的都是它。

Top-K 问题（从 $n$ 个数里找最大 / 最小的 $k$ 个，$n$ 极大而 $k$ 很小）是堆最典型的应用，做法是维护一个大小为 $k$ 的堆：

1. 用前 $k$ 个元素建堆（$O(k)$）；
2. 对剩下的 $n-k$ 个元素，逐个与堆顶比较 1 次：够不上门槛就直接丢弃（$O(1)$）；够得上就替换堆顶并调整（$O(\log k)$）；
3. 处理完，堆里就是要找的 $k$ 个。

时间 $O(n\log k)$，$k$ 是常数时就是 $O(n)$；空间只要 $O(k)$，且数据可以只过一遍、不必全部存下来。

用大根堆还是小根堆，是这里唯一容易想反的地方。 判据只有一句：

要淘汰谁，谁就放堆顶。

新元素来了要判断的是"它够不够格挤进 top-$k$"，而挤进去就要淘汰掉当前 $k$ 个里最没资格的那个。所以：

• 求最大的 $k$ 个 → 用小根堆（堆顶是这 $k$ 个里最小的，它最该被淘汰）；
• 求最小的 $k$ 个 → 用大根堆（堆顶是这 $k$ 个里最大的，它最该被淘汰）。

两种情形下堆顶都扮演门槛：一次比较就能淘汰掉绝大多数元素，这正是"平均比较次数尽可能少"的来源。

另有一个近亲问题：求第 $k$ 大。若 $n$ 不大，可以直接 $O(n)$ 建大根堆再删 $k-1$ 次堆顶，此时堆顶就是答案，时间 $O(n+k\log n)$、空间 $O(1)$。两种做法的分界是 $k$ 与 $n$ 的相对大小，以及数据能不能全部装下。

考点速记

三条会被反复调用的结论：

1. 堆 $=$ 完全二叉树 $+$ 堆序性：完全性换来数组存储与 $O(\log n)$ 的路径；堆序性只保证根是最值——整体无序，查任意元素 $O(n)$。
2. 上浮还是下沉，只看破坏的是上面还是下面的堆序；建堆必须自底向上倒着下沉，否则违反"两棵子树已是堆"。
3. 建堆 $O(n)$、堆排序 $O(n\log n)$：代价按结点高度加权、$\sum k/2^k=2$ 收敛；Top-K 用"要淘汰谁谁就放堆顶"来定用哪种堆。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。这是出题很密的一节，四类：

• 插入一个元素后，问调整结果或比较次数。 做法固定：新元素放末尾，然后一路上浮。问结果就把最终数组写出来，问次数就按"每层 1 次、含最后那次不用换的比较"数。
• 删除堆顶（或连删两次）后，问新堆。 做法固定：末元素填到根，然后下沉。连删两次就把这套动作做两遍，中间那一步的堆一定要写出来再做第二遍，凭印象跳步必错。比较次数按"完整两个孩子的层 2 次、只有一个孩子的层 1 次"数。
• 建堆过程的中间序列。 选项会给出四组"序列变化过程"，判断哪一组正确。做法是从 $\lfloor n/2\rfloor$ 倒着做下沉，每完成一个 $i$ 就把当前数组抄一遍去比对选项。注意选项里常混入"自顶向下插入建堆"的中间态。
• 关于堆的判断题。 逐条核对即可，三条为真、一条为假：堆是完全二叉树 ✓、可用顺序存储 ✓、堆不是二叉排序树 ✗（大根堆 5(3, 4) 满足堆序但违反 BST）、大根堆的次大值一定在根的下一层 ✓。
• Top-K 的算法设计大题。 例如"从十万个数里找最小的 10 个，要求平均比较次数尽可能少"。答案是维护大小为 10 的大根堆——注意是大根堆，堆顶是当前 10 个里最大的，充当门槛；每个新元素只需 1 次比较即可淘汰。时间 $O(n\log k)=O(n)$，空间 $O(k)=O(1)$。答题时要把"为什么用大根堆而不是小根堆"讲清楚，那是给分点。

易错：求最小的 $k$ 个用了小根堆。 记住"要淘汰谁，谁就放堆顶"。

易错：数比较次数时漏掉最后那次"发现不用交换"的比较，或者把下沉时的"两孩子互比"忘了算。

易错：把删除堆顶理解成"拿走根、合并两棵子堆"。 那会破坏完全二叉树形态，正确做法是末元素填根再下沉。

易错：认为在大根堆中查第 $k$ 大是 $O(1)$。 只有 $k=1$ 成立；$k\ge 2$ 时它可能藏在任何位置。

易错：建堆时正着从 1 走到 $\lfloor n/2\rfloor$。 必须倒着走，否则"两棵子树已是堆"的前提不成立。

教材出处

• 堆的定义（"$n$ 个元素的序列 $\{k_1,k_2,\dots ,k_n\}$ 称之为堆，当且仅当满足 $k_i\ge k_{2i}$ 且 $k_i\ge k_{2i+1}$，或 $k_i\le k_{2i}$ 且 $k_i\le k_{2i+1}$，$1\le i\le \lfloor n/2\rfloor$"）、"若将和此序列对应的一维数组看成是一个完全二叉树，则堆实质上是满足如下性质的完全二叉树：树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值"，以及"堆顶元素必为序列中 $n$ 个元素的最大值（或最小值）"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p250（8.3.2 节）
• 调整堆的"筛选法"及其比喻（"上述过程就像过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来"），以及算法 8.7 HeapAdjust 的完整实现——本篇 SiftDown 采用的正是它的"暂存 + 单向搬移"写法：印刷 p251
• 建初堆的原理（"只有一个结点的树必是堆，而在完全二叉树中，所有序号大于 $\lfloor n/2\rfloor$ 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，只需利用筛选法，从最后一个分支结点 $\lfloor n/2\rfloor$ 开始……"）与算法 8.8：印刷 p251
• 完全二叉树的编号性质（双亲 $\lfloor i/2\rfloor$、左孩子 $2i$、右孩子 $2i+1$）：印刷 p119–p120
• 插图见上文，取自殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）p237

说明：删除任意元素、修改优先级、Top-K 与优先队列的多种实现对照，在严蔚敏这本教材中没有对应章节（它把堆放在排序一章、只服务于堆排序），故不标页码；这几节为本文依据堆的基本性质自行推出。

相关知识

堆排序（排序流程在那篇）｜树与二叉树基本概念（下标公式来源）｜哈夫曼树｜二叉排序树｜Dijkstra｜Prim｜队列

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2024Q92分2022Q4210分2021Q112分2020Q92分2015Q102分2011Q112分2009Q92分