堆(Heap) 知识点讲解

概念

大白话：堆（Heap）就像是一个永远自动把“最厉害”的球顶在最上面的盒子。你往里面扔球，它会自动调整，保证每次你伸手去拿，拿到的永远是盒子里最大（或最小）的那个。在计算机里，这个“盒子”是一棵特殊的树，专门用来高效地管理一堆数据，让你不用每次都把数据重新排好序。

想象一下你在玩一个游戏，手里有一堆不同分数的卡片，每次你需要立刻知道哪张分数最高。如果你每次都用排序（比如冒泡排序）来找最大值，那每找一次都要花 $O(n)$ 的时间，找 $n$ 次就是 $O(n^2)$，太慢了！堆的作用就是让你每次找最大值或最小值只需要 $O(\log n)$ 的时间，而且插入新数据也很快。

为了让你理解为什么堆能做到这一点，我们先看一个极小的暴力例子：

假设有 3 个数：[5, 2, 8]。

• 普通排序找最大值：比较 5 和 2（5 大），比较 5 和 8（8 大）。找到 8。
• 堆的做法：把 8 直接放在最上面。如果你再插入一个 9，它立刻顶上；如果你把 8 拿走，剩下的 5 和 2 会自动调整，保证 5 顶上。整个过程就像水往低处流，大的自然浮上来。

这种结构在算法竞赛中被称为“优先队列”的底层实现。看到“动态维护极值”、“每次取最大/最小”、“合并代价最小”这些字眼时，堆就是最优解。

触发清单（看到这些信号第一时间想到本知识点）

定义

堆（heap） 是一棵完全二叉树，且满足“堆性质”：每个父结点的值都不大于（或不小于）它的两个子结点。

• 小根堆：父 ≤ 子，堆顶是最小值；
• 大根堆：父 ≥ 子，堆顶是最大值。

因为是完全二叉树，用数组存最省事：结点 i 的左右孩子在 2i 和 2i+1，父在 i/2（都从 1 开始编号）。

⚠️ 一句话：堆就是“随时能 O(1) 拿到最大/最小值、取走后 O(log n) 恢复”的结构。看到“每次取最大/最小、不断插入新值”，堆是最优解。

STL 优先队列（最常用，推荐）：

#include <queue>
priority_queue<int> pq; // 默认大根堆（堆顶最大）
priority_queue<int, vector<int>, greater<int>> minpq; // 小根堆
pq.push(x); int t = pq.top(); pq.pop(); // top 看堆顶，pop 删堆顶（都 O(log n)）

手写小根堆核心：向下调整（sift down）

int h[N], sz;
void down(int u) { // 结点 u 往下“沉”
 int v = u * 2;
 if (v > sz) return;
 if (v + 1 <= sz && h[v+1] < h[v]) v++; // 取较小的孩子
 if (h[v] < h[u]) { swap(h[u], h[v]); down(v); } // 孩子更小就交换并继续
}
void pop() { h[1] = h[sz--]; down(1); } // 堆顶用末尾覆盖再下沉
void push(int x) { h[++sz] = x; /* 上滤 */ while (x/2 && h[x] < h[x/2]) { swap(h[x],h[x/2]); x/=2; } }

三条铁律：

1. 默认 priority_queue 是大根堆；要小根堆必须显式写 greater<int>；

2. top() 只“看”不“删”，删用 pop()（无返回值）；空堆调用会 RE；

3. 堆只保证“堆顶是极值”，不保证整体有序，整体有序要不断 pop。

技巧速查表（背下来）

例题

例：合并果子（P1090 思路）—— 每次取最小的两堆合并，代价累加。

#include <iostream>
#include <queue>
using namespace std;
int main() {
 int n; cin >> n;
 priority_queue<long long, vector<long long>, greater<long long>> pq;
 for (int i = 0; i < n; i++) { long long x; cin >> x; pq.push(x); }
 long long ans = 0;
 while (pq.size() > 1) {
 long long a = pq.top(); pq.pop(); // 当前最小
 long long b = pq.top(); pq.pop(); // 当前次小
 ans += a + b; // 这次合并的体力
 pq.push(a + b); // 合成新堆放回
 }
 cout << ans << '\n';
 return 0;
}

为什么“每次合并最小俩”最优？因为越早合并的果子，后面会被再合并的次数越多，所以它对总代价的“权重”越大；让小的尽早、多次参与，总代价最小——这正是哈夫曼树的思想。

下面对照一张图理解“小根堆：父 ≤ 子，堆顶最小”：

例题复盘总结

例 1：合并果子（P1090）

• 共性特征：动态维护集合，每次取最小两个合并，总代价累加。
• 各自技巧：必须用小根堆（greater），注意 long long 防溢出。
• 审题模板：看到“合并”、“代价”、“最小” → 哈夫曼 → 小根堆。
• 错误清单：误用大根堆、用 sort 代替堆（$O(n^2 \log n)$）、忘记 long long。

例 2：动态中位数（P1168）

• 共性特征：动态插入数据，实时求中位数。
• 各自技巧：双堆法。大根堆存较小一半，小根堆存较大一半。插入时先入大堆，再把大堆顶移到小堆，若小堆比大堆多一个，再把小堆顶移回大堆。中位数在大堆顶。
• 审题模板：看到“中位数”、“动态”、“第 K 小” → 双堆。
• 错误清单：没平衡两堆大小（差超过 1）、空堆直接 top、忘记 greater。

写法总表

分工说明：触发清单用于“看到题干信号时快速定位知识点”，技巧速查表用于“背下核心 API 和手写模板”，写法总表用于“根据题目类型选择具体技法组合”。

常见错误

1. 搞反大根小根：priority_queue<int> 默认大根；要最小值用小根堆必须 greater<int>。

2. 空堆 top/pop：堆为空时调用会 RE，先 !empty()。

3. 误以为堆整体有序：堆只保证堆顶极值，其余只是局部有序；要全序就不断 pop。

4. 手写堆数组从 0 编号：左右孩子公式 2i/2i+1 只在“从 1 编号”时成立，从 0 编号要改公式。

5. 合并果子用排序：每次重新 sort 是 $O(n^2 \log n)$，用堆才是 $O(n \log n)$。

6. 双堆中位数没平衡大小：插入后要让两堆 size 差 ≤ 1，否则中位数取错。

7. long long 漏掉：合并果子 / 哈夫曼总代价可能爆 int，用 long long。

自测

1. 小根堆和大根堆分别保证什么？priority_queue<int> 默认是哪种？

2. 为什么堆的插入/删除是 $O(\log n)$ 而不是 $O(n)$？

3. 合并果子为什么“每次合并最小两堆”最优？这对应什么经典结构？

4. 动态求中位数为什么用“大根堆 + 小根堆”？两个堆各存什么？

5. 手写堆时，数组从 1 编号，结点 i 的左右孩子在哪？父结点呢？

6. 为什么“堆整体不是有序的”，只能保证堆顶是极值？

7. 求“前 K 小”应该用大根堆还是小根堆？为什么？

举一反三 · 审题流水线

1. 抓信号：读题圈出“最大/最小”、“合并”、“中位数”、“第 K 小”等关键词。

2. 定模型：信号对应堆、双堆还是贪心？若是堆，是大根还是小根？

3. 选写法：STL 能搞定吗？若需手写，数组从几开始编号？

4. 防陷阱：检查数据类型（long long）、空堆判断、平衡条件。

5. 写代码：按模板敲，边写边自测小样例。

练手题

题 1：动态极值查询

给定一个序列，支持两种操作：

1. 插入一个数。

2. 询问当前序列的最大值和最小值。

数据范围：$n, q \le 10^5$，数值范围 $10^9$。

提示：用一个小根堆维护最小值，一个大根堆维护最大值。

题 2：K 路归并

有 $K$ 个有序数组，每个数组长度不超过 $M$。请合并它们为一个有序数组，并输出前 $N$ 个元素。

数据范围：$K \le 100, M \le 10^5, N \le 10^7$。

提示：用堆存储每个数组当前的最小元素及其来源，每次取出堆顶放入结果，并将该数组的下一个元素入堆。