堆 · 全景梳理

反复要拿最值时，排序太贵、遍历太慢——堆是介于两者之间恰到好处的折中

目录
1. 堆的定义 2. 数组存储方式 3. 上浮与下沉 4. Push 与 Pop 4.5 删除任意元素 5. 建堆（heapify） 6. 堆排序 7. 总结：全景图

有一类需求反复出现：任务调度器要不断挑"最紧急的任务"先执行；Dijkstra 要不断挑"当前离起点最近的未访问节点"；合并 k 个有序链表要不断挑"k 个头节点里最小的那个"。共同点是——数据在不断增删，但每一步都要快速拿到当前的最值。

朴素的办法有两种，都不够好。一种是每次都重新排序或整体遍历一遍找最值——插入一次、删除一次就要付出 O(n) 甚至 O(n log n) 的代价，而且这次排的序，下次操作后大半就作废了。另一种是让数组时刻保持完全有序（插入时按位插入）——查最值是 O(1)，但插入要挪动数据，同样要 O(n)。两种做法都在为"用不上的信息"付费：要么排了序却只用得上最值，要么查得快却插入慢。

堆的思路是只维持"不完全的有序"——只保证父节点和子节点之间的大小关系，兄弟之间、跨层之间一概不管。用这一点点约束换来的是：拿最值 O(1)，插入和删除都只要 O(log n)。下面从它的定义开始。

1. 堆的定义

先看一个具体例子。

小顶堆（父 ≤ 子） 1 3 2 7 4 大根堆（父 ≥ 子） 7 5 3 1 4

左边这棵树：根 1，两个孩子分别是 3 和 2；2 的两个孩子是 7 和 4。逐层检查父子关系：1 ≤ 3，1 ≤ 2，2 ≤ 7，2 ≤ 4——每一层都满足父 ≤ 子。这就是一个合法的小顶堆。右边是对称的大根堆（父 ≥ 子）。

把这个例子里的规律抽象一下，堆要同时满足两个条件：

形状条件：必须是完全二叉树——除了最后一层，每层都填满；最后一层从左到右连续填，不能有空洞。

值条件（二选一）：大根堆（父 ≥ 子）或小根堆（父 ≤ 子）。

形式化定义（PDF / 王道）

若 n 个关键字序列 L[1…n]（下标从 1 起）满足以下某一条，则称为堆：

· 大根堆：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1)，其中 1 ≤ i ≤ ⌊n/2⌋
· 小根堆：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1)，其中 1 ≤ i ≤ ⌊n/2⌋

只约束到 ⌊n/2⌋，因为这正是最后一个非叶子节点——之后的都是叶子，没有子节点可比。

堆不关心左右孩子之间谁大谁小，只管父子关系。这和二叉搜索树（左 < 根 < 右）完全不同——注意看：小顶堆里 3 排在 2 的左边（3 > 2），堆不管兄弟大小关系。

现在我们知道堆长什么样——但普通二叉树通常靠左右指针挂在内存里，堆有没有更省的办法？

2. 数组存储方式

确实有。完全二叉树有个特权：每层从左到右填满、没有空洞，所以按层序把节点拍平进数组后，谁是谁的孩子光看下标就能算出来，一个指针都不用存。

1 [1] 3 [2] 2 [3] 7 [4] 4 [5] 数组： 11 32 23 74 45 左孩子 = 2i 右孩子 = 2i + 1 父节点 = ⌊i/2⌋

规则就是：左孩子 = 2i，右孩子 = 2i + 1，父节点 = ⌊i/2⌋（下标从 1 起）——这棵树按层序拍平后就是上图右下角那一排数组格子。

堆必须是完全二叉树——中间有空洞的话，数组里就得留空位，下标公式对不上。
注意下标起点：王道/课本从 1 开始（左孩子 = 2i，父 = i/2）；LeetCode 从 0 开始（左孩子 = 2i+1，父 = (i−1)/2）。本质一样，只差偏移。

下标关系解决了"父子是谁"，但没解决"数组乱了怎么办"——插入或删除一个元素后，某个位置可能瞬间不满足父子的大小关系，谁来把它修好？

3. 上浮与下沉

答案是两个方向相反的"原子动作"，堆的所有操作最终都靠它们兜底（以小顶堆为例）。

上浮（sift up）

某节点比父节点小，就和父节点交换；交换后再看新的父节点，直到父更小或到达根为止。

上浮前 9 3 15 → 上浮后 3 9 15

子节点 3 比父节点 9 小，违反小顶堆；交换后 3 成为新的父节点。如果它比"新父"还小，就继续往上比——一路比到根，或者比某一层的父节点大为止。

下沉（sift down）

某节点比子节点大，就和较小的子节点交换，直到比两个子都小或到达叶子为止。

下沉前 30 8 20 → 下沉后 8 30 20

根 30 比两个孩子都大，违反小顶堆；8 是两个孩子里更小的一个，8 上位后，30 沉到原来的位置，继续跟它新的孩子比。

为什么和"较小的子"交换？如果和较大的子交换，那个子到了父的位置后，可能比另一个子还大，堆性质还是不满足。

两个操作都沿树的高度走，复杂度都是 O(log n)——不需要碰树上其他任何节点。接下来看它们怎么撑起 push 和 pop。

4. Push 与 Pop

有了上浮和下沉，插入和取出元素就不用重新扫描整个堆——各自复用一个原子操作就够了：

操作步骤原子操作复杂度
Push新元素放到数组末尾，然后上浮上浮O(log n)
Pop取走根，末尾搬到根，数组缩短 1，然后下沉下沉O(log n)

为什么 push 用上浮、pop 用下沉？push 把新元素放到数组末尾（完全二叉树的下一个空位），它只可能比自己的祖先小，只会往上跑；pop 把堆底元素搬到根，它只可能比自己的子孙大，只会往下跑——插入点和删除点的位置，决定了修复的方向。

数组视角：

push 和 pop 处理的都是"数组的一端"（末尾或堆顶）。如果要删的是中间某个位置呢？

4.5 删除任意元素

Pop 只删根节点。但堆也支持删除任意位置的元素（PDF 例题）：直接把目标位置抠掉行不行？不行——那会在数组中间留一个洞，后面所有节点的下标关系全乱了，谁是谁的父母都算不出来。所以还是要借助堆底元素补位，再重新调整。

步骤：用堆底元素（数组最后一个）替换被删除的位置，数组缩短 1，然后对该位置做调整——可能需要下沉（替换值比子大），也可能需要上浮（替换值比父小），具体看它和新邻居的大小关系。

PDF 例题：删除元素 13

小顶堆 [09, 13, 65, 17, 45, 78, 87, 53, 32, 46]，删除下标 2 处的 13。

数组视角：
和 Pop 的关系：Pop 其实就是"删除下标 1（根）"的特殊情况。删除任意位置时，替换后的元素可能需要上浮也可能需要下沉，而 Pop 中替换后一定是下沉（因为堆底元素放到根，不可能比根的父节点更小——根没有父节点）。

至此，上浮、下沉、push、pop、删除都过了一遍——它们都是同一套机制的不同应用。剩下一个更大的问题：如果起点根本不是堆，而是一堆随机数，要怎么一次性"挤"成堆？

5. 建堆（heapify）

给一个无序数组，把它变成合法的堆。最直接的想法是：把每个元素当成"新数据"逐个 push 一遍——n 次 push，每次 O(log n)，总共 O(n log n)。这和"重新排序"没有本质区别，堆真正的优势没发挥出来。有没有更快的办法？

思路：叶子节点没有子节点，"父 ≤ 子"（或 ≥）的约束对它根本不存在，天然满足堆性质。所以只需要从最后一个非叶子节点开始，往前逐个做下沉——不用碰叶子，也不用像 push 那样从头开始。

为什么最后一个非叶子节点是 n/2 - 1（下标从 0 起）？

最后一个非叶子节点，就是数组最后一个元素的父节点——因为完全二叉树从左到右连续填，最后一个元素是"最靠右下"的节点，它的父节点之后的所有节点都不可能再有孩子。

数组最后一个元素的下标是 n-1，它的父节点下标是 ⌊(n-1-1)/2⌋ = ⌊(n-2)/2⌋。

这个公式用统一的 ⌊(i-1)/2⌋ 即可，不需要区分左右孩子。原因：

· 左孩子 i = 2p+1：⌊(2p+1-1)/2⌋ = p
· 右孩子 i = 2p+2：⌊(2p+2-1)/2⌋ = ⌊p + 1/2⌋ = p（整数向下取整）

而 ⌊(n-2)/2⌋ 在 C 的整数除法下等价于 n/2 - 1（可分 n 为奇偶验证）。

下标从 1 起的版本更简洁：最后一个元素下标为 n，父节点直接 n/2（整数除法）。这也是很多课本选择从 1 开始的原因——公式更干净。
时间复杂度 O(n)，不是 O(n log n)。大部分节点在底层，下沉路径短——这才是建堆比"逐个 push"快的根本原因。
代码视角（核心片段，联动下方每一步；完整版见下方）：
void HeadAdjust(int A[], int k, int len) {
A[0] = A[k];
for (int i = 2*k; i <= len; i *= 2) {
if (i < len && A[i] < A[i+1]) i++;
if (A[0] >= A[i]) break;
else { A[k] = A[i]; k = i; }
}
A[k] = A[0];
}
void BuildMaxHeap(int A[], int len) {
for (int i = len/2; i > 0; i--)
HeadAdjust(A, i, len);
}
数组视角：

代码(PDF / 王道，下标从 1 开始)

注意：以下代码下标从 1 开始，A[0] 用作临时存储。左孩子 = 2i，右孩子 = 2i+1，父 = i/2。这里建的是大根堆——和前面 push/pop 的小顶堆例子方向相反，原理完全对称（下沉挑较大的子而不是较小的子）。
// 将以 k 为根的子树调整为大根堆（下沉操作）
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];                          // A[0]暂存子树的根结点
    for (int i = 2*k; i <= len; i *= 2) { // 沿key较大的子结点向下筛选
        if (i < len && A[i] < A[i+1])
            i++;                          // 取key较大的子结点的下标
        if (A[0] >= A[i])  break;         // 筛选结束
        else {
            A[k] = A[i];                  // 将A[i]调整到双亲结点上
            k = i;                        // 修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];                          // 被筛选结点的值放入最终位置
}

// 建立大根堆
void BuildMaxHeap(int A[], int len) {
    for (int i = len/2; i > 0; i--)       // 从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
}

建堆结束后，数组变成了合法的大根堆 [7, 5, 3, 1, 4, 2]。如果不断把堆顶换到堆尾锁住、再对剩下的部分重新下沉，会发生什么？——那正是下一节的堆排序，而且它就从这个结果接着往下讲。

6. 堆排序

堆排序 = 建堆 + 反复"类 pop"。和 pop 的唯一区别：取出的元素不是返回给调用者，而是交换到数组末尾锁住。

Pop堆排序每一趟
操作记录根 → 末尾填根 → 缩短 → 下沉根和末尾交换 → 锁定末尾 → 下沉
结果去哪返回给调用者，离开数组留在数组末尾
升序排列用大根堆：每趟把最大值换到末尾锁住。
代码视角（核心片段，联动下方每一步；完整版见下方）：
void HeapSort(int A[], int len) {
BuildMaxHeap(A, len);
for (int i = len; i > 1; i--) {
swap(A[i], A[1]);
HeadAdjust(A, 1, i-1);
}
}
数组视角（■ 已排好锁定）：

代码(PDF / 王道，下标从 1 开始)

同样下标从 1 开始，复用上面的 HeadAdjust 和 BuildMaxHeap。
// 堆排序的完整逻辑
void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);                 // 初始建堆
    for (int i = len; i > 1; i--) {       // n-1趟的交换和建堆过程
        swap(A[i], A[1]);                 // 堆顶元素和堆底元素交换
        HeadAdjust(A, 1, i-1);            // 把剩余的待排序元素整理成堆
    }
}

算法效率分析（PDF）

指标值说明
建堆O(n)关键字对比次数不超过 4n
排序O(n log₂n)n-1 趟，每趟下沉最多 h-1 层，每下沉一层最多对比 2 次
总时间O(n log₂n)O(n) + O(n log₂n) = O(n log₂n)
空间O(1)原地排序，只需常数个辅助变量
稳定性不稳定见下方反例

为什么不稳定？

PDF 反例：初始序列 [1, 2, 2]（两个 2 分别记为 2a 和 2b）。

建大根堆后变为 [2a, 1, 2b]。第一趟堆排序：堆顶 2a 和末尾 2b 交换 → [2b, 1, 2a]。最终排好后 2b 排在 2a 前面——两个相等元素的相对顺序被打乱了。

至此，堆的核心机制——上浮、下沉，以及在它们之上搭建的 push/pop/建堆/排序——都过了一遍。最后串起来看全景。

7. 总结：全景图

回到开头的问题：反复要拿最值时，堆比"每次重排"和"插入即排序"都更划算——用 O(log n) 的插入/删除，换 O(1) 的查最值。

底层工具：上浮、下沉。

基于它们构建的操作：Push = 放末尾 + 上浮；Pop = 取根 + 末尾填根 + 下沉；建堆 = 从最后一个非叶子节点往前逐个下沉。

优先队列（如 mergeKLists）堆排序
堆的角色当"容器"，反复 push/pop原地排序
用到的操作push（上浮）、pop（下沉）建堆（下沉）、反复"交换 + 下沉"
堆类型按需求选升序用大根堆
总复杂度每次 O(log n)O(n log n)
核心教训：push/pop 和堆排序共享同一套底层机制（上浮/下沉），只是目的不同：一个是进进出出的容器，一个是原地排序的算法。
Made with claude-algo-visualize