堆的构造与操作 · 融合风（象牙 + Obsidian 入口）

速查

堆 = 完全二叉树 + 堆序性质，一维数组存储（$i$ 的孩子 $2i$、$2i+1$，父 $\lfloor i/2 \rfloor$）。建堆 O(n)，插入/删除 O(log n)，取最值 O(1)。

核心概念 ▾

堆（Heap）是满足堆序性质的完全二叉树：大根堆父 $\geq$ 子（根最大）；小根堆父 $\leq$ 子（根最小）。

堆用数组顺序存储：$i$ 的左孩子 $2i$、右孩子 $2i+1$、父节点 $\lfloor i/2 \rfloor$（下标从 1 开始，0 号位常作暂存）。

建堆（Heapify）—— 自下而上下滤

从最后一个非叶节点 $\lfloor n/2 \rfloor$ 开始，向前依次对每个节点执行下滤（sift down）到根。

void BuildMaxHeap(int A[], int n){
    for (int i = n/2; i >= 1; i--)
        AdjustDown(A, i, n);
}
void AdjustDown(int A[], int k, int n){
    A[0] = A[k];                       // 暂存
    for (int i = 2*k; i <= n; i *= 2){
        if (i < n && A[i] < A[i+1]) i++; // 选较大的子节点
        if (A[0] >= A[i]) break;
        A[k] = A[i]; k = i;            // 大孩子上移，继续下滤
    }
    A[k] = A[0];
}

插入 —— 尾部插入后上滤

新元素放到数组末尾，与父节点比较，若大于父节点则交换（上滤 / sift up），直到满足堆序。O(log n)。

删除堆顶 —— 末尾替换后下滤

堆顶与末尾元素交换，堆大小减 1，再对新的堆顶执行下滤。O(log n)。

关键性质 ▾

性质	说明
存储结构	完全二叉树，用数组存储
堆序性	大根堆 $A[\text{parent}] \geq A[\text{child}]$
建堆复杂度	O(n)，不是 O(n log n)
插入 / 删除堆顶	O(log n)（上滤 / 下滤最多到根或叶）
取堆顶	O(1)
堆排序	O(n log n)，不稳定

建堆时间 O(n) 的证明高度为 $h$ 的节点最多 $\lceil n/2^{h+1} \rceil$ 个，每个最多下滤 $h$ 次：$T(n) = \sum h \cdot \lceil n/2^{h+1} \rceil \approx n \sum \frac{h}{2^h} = n(\frac12+\frac24+\frac38+\cdots) = 2n = O(n)$。高节点少、低节点多，下滤总代价反而小。

常见考法 ▾

考法	解题套路
手动建堆	从 $\lfloor n/2 \rfloor$ 开始逐个下滤
堆插入 / 删除	插入→上滤；删除→末尾替换 + 下滤
建堆时间复杂度	O(n) 不是 O(n log n)，用级数求和证明
堆与排序	堆排序 = 反复取堆顶 + 下滤，O(n log n)
判断是否为堆	检查每个父节点与子节点的关系

易错点 ▾

易错清单

⚠️ 建堆是 O(n) 不是 O(n log n)——下滤工作量与节点高度成反比。
⚠️ 下滤时要选较大子节点（大根堆），不是随意选。
⚠️ 堆是完全二叉树但不一定是满二叉树。
⚠️ 数组下标从 1 开始，0 号位通常做暂存空间。
⚠️ 堆只保证堆顶是最值，不保证整体有序。

核心结论 ▾

堆 = 完全二叉树 + 堆序性质，用数组存储。
建堆 O(n)，插入 O(log n)，删除 O(log n)，取最值 O(1)。
建堆从最后一个非叶节点开始，自下而上下滤。
堆排序 = 建堆 + 反复取堆顶下滤，总时间 O(n log n)。
堆是实现优先队列的最佳数据结构。

记忆卡片 ▾

大根堆和小根堆的区别？

大根堆父 $\geq$ 子、根最大；小根堆父 $\leq$ 子、根最小。

建堆的时间复杂度？为什么？

O(n)。下滤次数与节点高度成反比，高节点少、低节点多。

建堆从哪个节点开始？

最后一个非叶节点 $\lfloor n/2 \rfloor$，向前到根节点 1。

插入 / 删除如何维护堆？

插入：尾部上滤；删除：堆顶与末尾交换、堆大小减 1，新堆顶下滤。

交互动画 · 建堆 / 插入 / 删除 ▾

初始数组 53,17,78,9,45,65,87 —— 准备建大根堆

点「建堆 · 下滤下一步」：从 ⌊n/2⌋=3 号开始自下而上下滤

建堆 O(n)；插入 100（尾部上滤）、删除堆顶（末尾替换 + 下滤）各 O(log n)。

核心概念 ▾

建堆（Heapify）—— 自下而上下滤

插入 —— 尾部插入后上滤

删除堆顶 —— 末尾替换后下滤

关键性质 ▾

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 建堆 / 插入 / 删除 ▾

相关知识点