排序之后取最大值很快,但一边插入新元素一边反复取最大值,排序就不够用了。堆就是为这种场景设计的:插入和取最值都是 O(\log n),而且取最值只要 O(1)。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| CSP-J/S 提高级 | 2.3.1 优先队列;2.3.3 二叉堆 | 全章 |
| GESP C++ 六级 | 考点 6:面向对象(堆的封装思路) | 数组模拟堆 |
堆是什么
堆是一棵完全二叉树,同时满足堆序性质:
- 大根堆:每个节点的值都不小于它的孩子,根是整棵树的最大值。
- 小根堆:每个节点的值都不大于它的孩子,根是整棵树的最小值。
因为是完全二叉树,堆可以直接用数组存。下标从 1 开始,节点 i 的关系是:
| 关系 | 下标 |
|---|---|
| 左孩子 | 2i |
| 右孩子 | 2i + 1 |
| 父节点 | \lfloor i / 2 \rfloor |
数组里看到的值不整体有序,但根一定是这个堆里的最值。这是堆和排序数组的关键区别。
两个核心操作
堆的调整围绕两个动作:上浮和下沉。
上浮(插入)
新元素放到数组末尾,然后不断和父节点比较。小根堆里如果它比父节点小就交换,直到比父节点大或者到了根。
int heap[100005], sz = 0; // 小根堆
void push(int x) {
heap[++sz] = x;
int i = sz;
while (i > 1 && heap[i] < heap[i / 2]) {
swap(heap[i], heap[i / 2]);
i /= 2;
}
}一次上浮最多走树高,复杂度 O(\log n)。
下沉(删除堆顶)
把根和末尾元素交换,删掉末尾,然后让新根不断和较小的孩子比较。小根堆里如果它比孩子大就往下换。
void sink(int i) { // 让 heap[i] 往下沉,直到满足堆序
while (true) {
int l = 2 * i, r = 2 * i + 1, smallest = i;
if (l <= sz && heap[l] < heap[smallest]) smallest = l;
if (r <= sz && heap[r] < heap[smallest]) smallest = r;
if (smallest == i) break;
swap(heap[i], heap[smallest]);
i = smallest;
}
}
void pop() {
heap[1] = heap[sz--]; // 末尾元素提到根
sink(1); // 再让它沉下去
}
int top() { return heap[1]; } // 堆顶就是最小值,O(1)建堆
把一个无序数组调整成堆,从最后一个非叶子节点开始,依次往前做下沉。
void build() {
for (int i = sz / 2; i >= 1; i--) sink(i);
}虽然每次下沉是 O(\log n),但对所有节点求和之后总复杂度是 O(n),不是 O(n \log n)。这个结论常考:建堆可以在线性时间内完成。
STL 的 priority_queue
竞赛里几乎不用手写堆,直接用 priority_queue。
#include <bits/stdc++.h>
using namespace std;
int main() {
priority_queue<int> pq; // 默认大根堆
pq.push(3);
pq.push(1);
pq.push(4);
cout << pq.top() << endl; // 4,取最大值
pq.pop();
// 小根堆要写全模板参数
priority_queue<int, vector<int>, greater<int>> minpq;
minpq.push(3);
minpq.push(1);
cout << minpq.top() << endl; // 1
return 0;
}pair 自带比较规则,先比第一个再比第二个,所以存 pair<int,int> 时,默认按第一个值从大到小。
要自定义优先级,可以写比较结构体:
struct Node { int id, dis; };
struct Cmp {
bool operator()(const Node &a, const Node &b) const {
return a.dis > b.dis; // 想取 dis 最小的,这里写大于
}
};
priority_queue<Node, vector<Node>, Cmp> pq;这里的 > 是反直觉的:priority_queue 的队头是「优先级最高」的元素,而比较函数定义的是排序关系,所以想让小值优先,比较函数里要写 a.dis > b.dis。
堆的典型应用
- 堆排序。反复取堆顶输出,时间
O(n \log n),额外空间O(1)。 - Top K 问题。求前
k大的元素,用一个大小为k的小根堆,扫描时把比堆顶大的挤进去,最后堆里就是答案。 - 合并果子。每次取两个最小的合并,用小根堆实现贪心。
- Dijkstra 最短路优化。用堆维护当前距离最小的点,复杂度从
O(V^2)降到O(E \log V)。 - 任务调度。按优先级取出下一个要执行的任务。
合并果子的例子:有 4 堆果子,数量分别是 1、2、3、4,每次合并两堆,代价是两堆数量之和,求最小总代价。
每次取最小的两堆:合并 1 和 2 得 3,代价 3;再合并 3 和 3 得 6,代价 6;合并 4 和 6 得 10,代价 10。总代价 3 + 6 + 10 = 19。
这正好是哈夫曼树的构造过程,总代价就是带权路径长度。
复杂度
| 操作 | 复杂度 |
|---|---|
| 取堆顶 | O(1) |
| 插入 | O(\log n) |
| 删除堆顶 | O(\log n) |
| 建堆 | O(n) |
| 查找任意元素 | O(n) |
堆不擅长查找任意值,也不支持删除任意元素。要删除任意元素,得用能定位元素的高级结构。
常见易错点
- 堆不保证整体有序,只保证根是最值,别用堆来做「有序遍历」。
priority_queue默认是大根堆,小根堆要用greater<int>。priority_queue只能访问堆顶,top()之前先判断非空。- 手写堆时下标从 1 开始,从 0 开始父子下标关系会变。
- 建堆是
O(n),不要以为必须O(n \log n)才行。 - 自定义比较函数的方向容易反,写完拿两个数据试一下。
- 该用小根堆的地方写成了默认的大根堆。合并果子、Top K 都必须显式传
greater<T>,忘了greater会静默给出错误答案。 - 求第
k大用大根堆。方向搞反了:求第k大要用小根堆(淘汰最小的),求第k小要用大根堆。 - 合并果子的答案用了
int。n和a_i都不大,但累加起来的代价会超出int。
练习
练习 1:合并果子
在线评测练习:P1422 合并果子
题目描述
果园里有 n 堆果子,第 i 堆有 a_i 个。每次可以任选两堆合并成一堆,代价为两堆果子数之和。经过 n - 1 次合并后只剩一堆,求最小总代价。
输入格式
第一行包含一个正整数 n;第二行包含 n 个正整数 a_1, a_2, \ldots, a_n,相邻两个整数之间用一个空格隔开。
输出格式
输出一行一个整数,表示最小总代价。
输入输出样例
输入
3
1 2 9输出
15(先合并 1 和 2,代价 3;再把 3 和 9 合并,代价 12。总代价 3 + 12 = 15。)
数据范围
1 \le n \le 10^4,1 \le a_i \le 2 \times 10^4。答案可能超出int,请用long long。
题目分析
这是堆最经典的应用,也是贪心和堆结合的入门题。
为什么每次取最小的两堆? 因为先被合并的堆会被反复计入后续的代价里(它变成新堆的一部分,之后每次合并都带着它走)。所以越小的堆应该越早合并、被计入的次数越多——这正好是哈夫曼树的思想。反过来,如果先把大的合并,大数会被反复计入,总代价必然更大。
为什么必须用堆? 因为每合并一次就要「重新找出最小的两个」。如果用数组每次排序或线性扫描,复杂度是 O(n^2 \log n) 或 O(n^2);用小根堆,插入和取最小都是 O(\log n),总复杂度 O(n \log n)。
代码骨架非常简单:
- 把所有果子数推进小根堆;
- 只要堆里还有 2 个以上元素:弹出最小的两个,求和,把和累加进
ans,再把和推回堆; - 最后输出
ans。
两个必须注意的点:
long long。n = 10^4、a_i = 2 \times 10^4时,总代价可能到10^9量级甚至更高,且中间累加更容易溢出。堆的元素类型和ans都用long long。- 小根堆的写法。默认
priority_queue<long long>是大根堆,会取出最大的两个,答案完全错。必须写全priority_queue<long long, vector<long long>, greater<long long>>。这是本题最大的坑——代码看起来没问题,思路也对,就是忘了greater,答案偏大。
参考代码
pq.size() > 1 这个循环条件很关键:只剩一堆时不需要再合并,循环自然结束。不需要单独处理 n = 1 的情况,因为一个元素时循环一次都不进,ans 保持 0,正是正确答案。
练习 2:第 k 大的数(Top K)
题目描述
给定 n 个整数和一个整数 k,求第 k 大的数(重复的数分别占位,即从大到小排序后第 k 个)。
输入格式
第一行两个整数 n 和 k;第二行 n 个整数。
输出格式
输出一个整数,表示第 k 大的数。
输入输出样例
输入
5 2
10 4 7 1 9输出
9数据范围
1 \le k \le n \le 10^5,元素在int范围内。
题目分析
这题有两条思路,恰好能对比出堆的价值:
思路一:全排序取第 k 个。 sort 一下,复杂度 O(n \log n)。n = 10^5 完全够用,实战中优先这么写。
思路二:大小为 k 的小根堆。 这是 Top K 问题的标准解法,复杂度 O(n \log k):
- 用小根堆维护「目前见过的最大的
k个数」; - 每读入一个数就推进堆;
- 如果堆大小超过
k,就弹出堆顶(堆里最小的那个); - 扫完之后,堆里正好是最大的
k个数,而堆顶就是第k大。
为什么小根堆能做到这件事? 因为小根堆的堆顶是「这 k 个里面最小的」,也就是「第 k 大」。每次新来的数如果比堆顶大,就把它挤掉——堆里始终只保留最大的 k 个。
什么时候思路二才有优势?
- 数据是流式来的(不能全部存下来再排序),比如从日志里实时找前
k个最大的; n极大(比如10^8)而k很小(比如 10),此时O(n \log k)远优于O(n \log n);- 内存不够存全部数据。
本题 n \le 10^5,两种都能过。但**「用大小为 k 的堆维护 Top K」这个技巧必须掌握**,它是堆最重要的应用模式之一。
一个容易想错的地方:求「第 k 大」用小根堆,求「第 k 小」用大根堆。直觉上是反的,但道理很清楚——要淘汰的是「最不可能是答案的那一端」。求第 k 大时,堆顶是这 k 个里最小的,它最该被更大的数淘汰,所以用小根堆。
参考代码
小结
- 堆是完全二叉树加堆序性质,根是全局最值。
- 堆用数组存储,父子下标关系是
2i、2i+1和\lfloor i/2 \rfloor。 - 插入靠上浮,删除堆顶靠下沉,都是
O(\log n);建堆可以O(n)。 - 竞赛里用
priority_queue,默认大根堆,小根堆要传greater。 - 堆的典型应用是堆排序、Top K、合并果子和 Dijkstra 优化。
- 合并果子:每次取最小的两个合并,必须用小根堆,答案用
long long。 - Top K:用大小为
k的堆,超过k就弹出堆顶。求第k大用小根堆,求第k小用大根堆。 - 能全排序解决时优先排序(
O(n \log n)常数小);数据流式或n极大而k很小时,才必须用大小为k的堆。