1. 核心概念:堆顶优先级最高#
1.1 基本定义#
#include <queue>
std::priority_queue<int> pq;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
priority_queue<int> pq;cpp默认行为:
pq.push(10);
pq.push(30);
pq.push(20);
cout << pq.top(); // 30:当前最大值cpp1.2 不是 FIFO,也不是全局有序数组#
- 普通 queue:先入先出。
- priority_queue:优先级高者先出,与入队先后无必然关系。
- 堆只保证堆顶满足优先级要求,不保证所有元素按完整顺序排列。
- 不能直接遍历得到一个有序序列;不断
top + pop才能依次取出优先级顺序。
1.3 大根堆的堆序#
默认大根堆中,父节点的值不小于子节点。堆顶是最大值,但左右子树之间不要求完整排序,兄弟节点也没有全局大小顺序。
1.4 允许重复元素#
priority_queue 可以保存任意多个相同值,不需要像 set 那样担心唯一性。
2. priority_queue 是容器适配器#
完整模板形式:
template<
class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type>
> class priority_queue;cpp因此:
priority_queue<int> pq;
// 等价于
priority_queue<int, vector<int>, less<int>> pq2;cpp三个模板参数分别是:
- 元素类型。
- 底层容器,默认 vector。
- 比较器,默认 less,因此是大根堆。
底层容器需要随机访问,并支持 front、push_back、pop_back。常用 vector,也可使用 deque;list 不适合作为堆的底层容器,因为堆调整需要随机访问。
priority_queue<int, deque<int>> a; // 默认仍是大根堆cpp竞赛通常使用默认 vector 即可。
3. 大根堆与小根堆#
3.1 默认大根堆#
priority_queue<int> maxHeap;cpp堆顶是最大值。
3.2 小根堆#
priority_queue<int, vector<int>, greater<int>> minHeap;cpp堆顶是最小值。
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
cout << minHeap.top(); // 10cpp3.3 pair 与 tuple 的堆#
pair 默认按字典序比较:
using PII = pair<int,int>;
priority_queue<PII> maxHeap2; // first 大者优先,再比较 second
priority_queue<PII, vector<PII>, greater<PII>> minHeap2; // 完整字典序小根堆cpp例如 {dist,node} 的小根堆:先取距离最小者;距离相同,再取节点编号较小者。
3.4 基本类型的负数技巧#
pq.push(-x);
int x = -pq.top();cpp大根堆存 -x 可以模拟小根堆,但一般不建议作为通用习惯:
- 可读性较差。
- 对最小可表示整数取负可能溢出。
- 复合类型不适用。
明确使用 greater<T> 更稳妥。
4. 核心接口#
4.1 插入:push 与 emplace#
priority_queue<int> pq;
pq.push(10);
int x = 20;
pq.push(x); // 拷贝
pq.push(move(x)); // 移动,之后不要依赖 x 原值
pq.emplace(30); // 原位构造cpp复合类型:
priority_queue<pair<int,int>> states;
states.push({1, 2});
states.emplace(3, 4);cpp插入后通过向上调整维护堆序,时间 O(log n)。
4.2 读取堆顶:top#
cout << pq.top();cpp空堆调用 top() 是未定义行为。
top() 返回 const 引用,不能直接修改堆顶:
// pq.top() = 100; // 错误cpp任意修改堆顶可能破坏堆序。需要修改时,通常取出旧元素,再插入修改后的元素。
4.3 删除堆顶:pop#
pq.pop(); // 删除堆顶,不返回元素cpp正确读取并删除:
int x = pq.top();
pq.pop();cpp错误写法:
// int x = pq.pop(); // 错:pop() 返回 voidcpp空堆调用 pop() 是未定义行为。删除后通过向下调整维护堆序,时间 O(log n)。
4.4 大小、判空与交换#
pq.size();
pq.empty();
a.swap(b);cpp交换时元素、底层容器和比较器类型必须匹配。
5. 构造与初始化#
5.1 空堆后逐个插入#
priority_queue<int> pq;
for (int x : a) pq.push(x); // n 次插入,O(n log n)cpp5.2 从已有区间建堆#
vector<int> a = {3, 1, 4, 2, 5};
priority_queue<int> pq(a.begin(), a.end());cpp从已有元素建堆通常为 O(n),优于逐个 push 的 O(n log n)。
小根堆:
priority_queue<int, vector<int>, greater<int>> pq2(
a.begin(), a.end(), greater<int>()
);cpp5.3 清空#
priority_queue 没有 clear():
pq = priority_queue<int>();cpp或使用同类型空堆 swap。自定义比较器的堆在重置时也要保持相同类型,不能直接赋成另一个不同类型。
6. 自定义比较器#
6.1 最重要的理解#
比较器决定“谁排在堆顶”:
less<T>:值大的优先,得到大根堆。greater<T>:值小的优先,得到小根堆。
对自定义比较器 cmp(a,b),可以粗略理解为:返回 true 表示 a 的优先级低于 b,a 应该更靠后。这与 sort 中“a 是否应排在 b 前面”的直觉不同,是高频易错点。
6.2 自定义结构体小根堆#
struct Node {
int dist;
int id;
};
struct Cmp {
bool operator()(const Node &a, const Node &b) const {
if (a.dist != b.dist) return a.dist > b.dist;
return a.id > b.id;
}
};
priority_queue<Node, vector<Node>, Cmp> pq;cpp此比较器让 dist 小者优先;dist 相同时 id 小者优先。
6.3 使用 lambda#
auto cmp = [](const Node &a, const Node &b) {
if (a.dist != b.dist) return a.dist > b.dist;
return a.id > b.id;
};
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);cpplambda 的类型必须通过 decltype(cmp) 指定,并在构造时传入比较器对象。
6.4 比较器要求#
比较器必须满足严格弱序:
- 对同一个元素不能出现
cmp(x,x)==true。 - 不要写
<=或>=代替严格比较。 - 不要用可能整数溢出的减法判断大小。
// return a.dist - b.dist > 0; // 不推荐,可能溢出
return a.dist > b.dist; // 正确cpp7. 复杂度#
设堆中有 n 个元素:
| 操作 | 时间复杂度 |
|---|---|
top() |
O(1) |
push() / emplace() |
O(log n) |
pop() |
O(log n) |
size() / empty() |
O(1) |
| 从 n 个已有元素建堆 | O(n) |
| n 次逐个插入 | O(n log n) |
| 全部弹出 | O(n log n) |
| 拷贝整个 priority_queue | O(n) |
swap |
通常 O(1) |
空间复杂度为 O(n),另加元素自身的存储成本。
priority_queue 不支持任意元素的查找、删除和修改,也没有 decrease-key 接口。
8. 应用一:Dijkstra 与懒惰删除#
8.1 为什么需要优先队列#
Dijkstra 每次需要取出当前未确定节点中距离最小者。小根堆保存 {当前距离,节点},可以高效取得这个状态。
8.2 标准模板#
using State = pair<long long,int>; // {dist, node}
vector<long long> dist(n + 1, LLONG_MAX / 4);
priority_queue<State, vector<State>, greater<State>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue; // 过期状态,懒惰删除
for (auto [v, w] : g[u]) { // 边为 {v,w}
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}cpp8.3 为什么允许重复入堆#
当发现更短距离时,priority_queue 无法直接修改堆中已有的旧状态,因此:
- 直接插入新的更优状态。
- 旧状态仍留在堆里。
- 旧状态以后到达堆顶时,通过
d != dist[u]跳过。
这就是懒惰删除。优点是实现简单,不需要定位任意堆元素。
8.4 注意事项#
- Dijkstra 要求边权非负。
- 堆中可能存在同一节点的多个状态,不要误以为每个节点只出现一次。
- 松弛成功才 push,新距离必须确实更优。
- 懒惰删除版本中堆状态数可能达到
O(E);复杂度常写为O((V+E)log V),同时要注意堆空间开销。 - 使用 long long 时防止距离和加法溢出。
9. 应用二:Top-K#
9.1 找最大的 k 个元素:维护大小为 k 的小根堆#
vector<int> topK(const vector<int> &a, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
if ((int)pq.size() < k) {
pq.push(x);
} else if (x > pq.top()) {
pq.pop();
pq.push(x);
}
}
vector<int> ans;
while (!pq.empty()) {
ans.push_back(pq.top());
pq.pop();
}
return ans; // 弹出结果为升序
}cpp堆顶是已保留 k 个元素中的最小值。如果新元素连它都不超过,就不可能进入前 k。
时间 O(n log k),空间 O(k)。适用于 k 明显小于 n 的情况。
9.2 找最小的 k 个元素#
反过来维护大小为 k 的大根堆:新元素小于堆顶时替换堆顶。
9.3 边界条件#
- 若 k 为 0,不应调用空堆 top;实际代码需直接返回。
- 若 k >= n,可直接保留全部元素。
- 示例核心代码假设
1 <= k <= n。 - 若只需要第 k 大元素,
nth_element平均O(n)也可作为选择;需要在线处理或流式数据时堆更自然。
10. 应用三:合并多个有序序列#
每个序列将当前最小元素放入小根堆,堆状态同时记录来源:
struct State {
int value;
int listId;
int index;
};
struct Cmp {
bool operator()(const State &a, const State &b) const {
return a.value > b.value; // value 小者优先
}
};
priority_queue<State, vector<State>, Cmp> pq;cpp基本步骤:
- 将每个非空序列的首元素入堆。
- 取出堆顶并加入答案。
- 将同一序列的下一个元素入堆。
- 直到堆空。
若共有 N 个元素、k 个序列,时间 O(N log k),堆空间 O(k)。
11. 应用四:双堆维护动态中位数#
low:大根堆,保存较小一半,堆顶是这部分最大值。high:小根堆,保存较大一半,堆顶是这部分最小值。- 保持
low的所有值不大于high,且两部分大小差不超过 1。
class MedianFinder {
priority_queue<int> low;
priority_queue<int, vector<int>, greater<int>> high;
public:
void add(int x) {
if (low.empty() || x <= low.top()) low.push(x);
else high.push(x);
if (low.size() > high.size() + 1) {
high.push(low.top());
low.pop();
} else if (high.size() > low.size()) {
low.push(high.top());
high.pop();
}
}
double median() const {
// 调用前提:至少有一个元素
if (low.size() > high.size()) return low.top();
return (low.top() + high.top()) / 2.0;
}
};cpp每次插入 O(log n),查询中位数 O(1)。双堆维护顺序统计量,比每次排序高效。
12. 其他竞赛应用与稳定性#
常见场景:
- 贪心选择当前最优资源或任务。
- Huffman 合并:每次取两个最小权值。
- 任务调度、会议室分配、事件模拟。
- Prim 最小生成树的堆优化。
- A* 等启发式搜索中的开放列表。
- 在线数据流的 Top-K 与动态顺序统计。
相同优先级不保证稳定#
priority_queue 不保证相同优先级元素按插入顺序出堆。若要求稳定,需要加入递增序号作为第二关键字:
using Item = pair<int,int>; // {priority, sequence}cpp然后根据需求使用大根堆、小根堆或自定义比较器,明确序号应按升序还是降序处理。
13. priority_queue 没有哪些功能#
// pq[0]; // 错误:没有随机访问
// pq.begin(), pq.end(); // 错误:没有公开迭代器
// for (int x : pq) {} // 错误:不能范围遍历
// pq.front(); // 错误:堆顶接口是 top
// pq.clear(); // 错误:没有 clear
// pq.reserve(n); // 错误:适配器不暴露 reserve
// pq.erase(x); // 错误:不能任意删除cpp遍历只能消费式弹出:
while (!pq.empty()) {
cout << pq.top() << ' ';
pq.pop();
}cpp若保留原堆,先复制再遍历,但复制为 O(n)。
需要堆操作又想访问数组#
可直接在 vector 上使用堆算法:
make_heap(a.begin(), a.end()); // 建大根堆
a.push_back(x); push_heap(a.begin(), a.end()); // 插入
pop_heap(a.begin(), a.end()); int x = a.back(); a.pop_back(); // 取堆顶
sort_heap(a.begin(), a.end()); // 堆排序cpp这组算法适合需要自己控制底层数组的场景,但接口比 priority_queue 更容易误用。
14. 与其他容器的选型#
| 需求 | 推荐容器 |
|---|---|
| 只关心当前最大/最小值,动态插入删除堆顶 | priority_queue |
| 先进先出 BFS | queue |
| 后进先出 DFS | stack/vector |
| 需要完整有序、二分查找、任意值删除 | set/multiset |
| 只需静态排序 | vector + sort |
| 只需一次第 k 大/小 | nth_element 可考虑平均 O(n) |
| 双端操作、滑动窗口最值 | deque |
与 multiset 对比#
- priority_queue:top
O(1),push/popO(log n),不能任意查找删除。 - multiset:完整有序,可
find/erase/lower_bound,插入删除通常O(log n),但节点开销一般更大。 - 只需要最值时堆通常更轻量;需要任意顺序查询时选 multiset。
15. 高频错误与避坑清单#
15.1 忘记默认是大根堆#
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;cpp15.2 自定义比较器方向写反#
sort 比较器与 priority_queue 的优先级直觉不同。写完比较器后用两三个样例验证堆顶,不要只凭感觉。
15.3 空堆 top/pop#
if (!pq.empty()) {
auto x = pq.top();
pq.pop();
}cpp15.4 把 pop 当成返回值的函数#
必须先 top,再 pop。
15.5 修改 top 或保存引用后 pop#
top 返回 const 引用,不能直接修改;pop 后原堆顶引用失效,应在 pop 前复制需要的数据。
15.6 误以为堆内部已经排序#
堆只保证堆序。不能遍历内部获得有序序列,也不能假设第二个元素就是整个堆的第二关键字顺序位置。
15.7 试图任意删除或修改元素#
priority_queue 没有 decrease-key/erase。Dijkstra 等场景通常使用新状态入堆加过期状态跳过。
15.8 相同优先级要求稳定却未加序号#
堆不稳定。需要稳定顺序时必须显式增加时间戳或输入下标。
15.9 比较器溢出或不满足严格弱序#
使用 </>,不要用相减;不要用 <=/>= 作为严格排序比较。
15.10 Top-K 选反堆类型#
- 最大 k 个:小根堆,堆顶是当前保留者中的最小值。
- 最小 k 个:大根堆,堆顶是当前保留者中的最大值。
16. 一页速记#
#include <queue>
priority_queue<int> maxHeap; // 默认大根堆
priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆
pq.push(x); // O(log n)
pq.emplace(x);
pq.top(); // O(1),空堆禁止
pq.pop(); // O(log n),返回 void,空堆禁止
pq.size(); pq.empty();
if (!pq.empty()) {
auto x = pq.top();
pq.pop();
}
pq = priority_queue<int>(); // 重置同类型空堆
// pair:字典序
using State = pair<long long,int>; // {dist,node}
priority_queue<State, vector<State>, greater<State>> dijkstra;
dijkstra.push({dist, u});
auto [d, u] = dijkstra.top();
dijkstra.pop();
if (d != dist[u]) { /* 过期状态 */ }
// 自定义小根堆比较器
struct Node { int dist, id; };
struct Cmp {
bool operator()(const Node &a, const Node &b) const {
if (a.dist != b.dist) return a.dist > b.dist;
return a.id > b.id;
}
};
priority_queue<Node, vector<Node>, Cmp> custom;
// 从数组 O(n) 建堆
priority_queue<int> built(a.begin(), a.end());
// 最大 k 个:大小为 k 的小根堆
priority_queue<int, vector<int>, greater<int>> topK;
for (int x : a) {
if ((int)topK.size() < k) topK.push(x);
else if (x > topK.top()) {
topK.pop();
topK.push(x);
}
}cpp最终必须牢牢记住:
- priority_queue 默认是大根堆,
greater<T>构造小根堆。 top()为O(1),push/pop()为O(log n)。- 堆只保证堆顶优先级,不保证内部全局有序。
pop()不返回值,空堆不能 top/pop。- 自定义比较器方向容易与 sort 混淆,必须用小样例验证。
- pair 堆按字典序,
{dist,node}是 Dijkstra 的常见状态。 - 不支持 decrease-key,通常用重复入堆和过期状态跳过。
- 最大 k 个元素维护小根堆,最小 k 个维护大根堆。
- 相同优先级不稳定,需要时增加序号。