堆 · 全景梳理

从定义到堆排序，一次串起来

1. 堆的定义

堆要同时满足两个条件：

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

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

形式化定义（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. 数组存储方式

堆不用链式结构，直接用数组按层序存储。父子关系靠下标算：

3. 上浮与下沉

堆的所有操作都建立在这两个"原子动作"上（以小顶堆为例）：

上浮（sift up）

某节点比父节点小，不断和父交换往上走，直到父更小或到达根。

下沉（sift down）

某节点比子节点大，不断和较小的子交换往下走，直到比两个子都小或到达叶子。

两个操作都沿树的高度走，复杂度 O(log n)。

4. Push 与 Pop

4.5 删除任意元素

Pop 只删根节点。但堆也支持删除任意位置的元素（PDF 例题）：

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

PDF 例题：删除元素 13

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

5. 建堆（heapify）

给一个无序数组，把它变成合法的堆。

思路：叶子节点没有子节点，"父 ≤ 子"的约束对它根本不存在，天然满足堆性质。所以只需要从最后一个非叶子节点开始，往前逐个做下沉。

为什么最后一个非叶子节点是 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 为奇偶验证）。

代码（PDF / 王道，下标从 1 开始）

// 将以 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);
}

6. 堆排序

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

代码（PDF / 王道，下标从 1 开始）

// 堆排序的完整逻辑
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）

为什么不稳定？

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

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

7. 总结：全景图

底层工具：上浮、下沉。

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