麦地

Back

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:当前最大值
cpp

1.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

三个模板参数分别是:

  1. 元素类型。
  2. 底层容器,默认 vector。
  3. 比较器,默认 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(); // 10
cpp

3.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() 返回 void
cpp

空堆调用 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)
cpp

5.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>()
);
cpp

5.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);
cpp

lambda 的类型必须通过 decltype(cmp) 指定,并在构造时传入比较器对象。

6.4 比较器要求#

比较器必须满足严格弱序:

  • 对同一个元素不能出现 cmp(x,x)==true。
  • 不要写 <= 或 >= 代替严格比较。
  • 不要用可能整数溢出的减法判断大小。
// return a.dist - b.dist > 0; // 不推荐,可能溢出
return a.dist > b.dist;        // 正确
cpp

7. 复杂度#

设堆中有 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 标准模板#

8.3 为什么允许重复入堆#

当发现更短距离时,priority_queue 无法直接修改堆中已有的旧状态,因此:

  1. 直接插入新的更优状态。
  2. 旧状态仍留在堆里。
  3. 旧状态以后到达堆顶时,通过 d != dist[u] 跳过。

这就是懒惰删除。优点是实现简单,不需要定位任意堆元素。

8.4 注意事项#

  • Dijkstra 要求边权非负。
  • 堆中可能存在同一节点的多个状态,不要误以为每个节点只出现一次。
  • 松弛成功才 push,新距离必须确实更优。
  • 懒惰删除版本中堆状态数可能达到 O(E);复杂度常写为 O((V+E)log V),同时要注意堆空间开销。
  • 使用 long long 时防止距离和加法溢出。

9. 应用二:Top-K#

9.1 找最大的 k 个元素:维护大小为 k 的小根堆#

堆顶是已保留 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

基本步骤:

  1. 将每个非空序列的首元素入堆。
  2. 取出堆顶并加入答案。
  3. 将同一序列的下一个元素入堆。
  4. 直到堆空。

若共有 N 个元素、k 个序列,时间 O(N log k),堆空间 O(k)。


11. 应用四:双堆维护动态中位数#

  • low:大根堆,保存较小一半,堆顶是这部分最大值。
  • high:小根堆,保存较大一半,堆顶是这部分最小值。
  • 保持 low 的所有值不大于 high,且两部分大小差不超过 1。

每次插入 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/pop O(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;
cpp

15.2 自定义比较器方向写反#

sort 比较器与 priority_queue 的优先级直觉不同。写完比较器后用两三个样例验证堆顶,不要只凭感觉。

15.3 空堆 top/pop#

if (!pq.empty()) {
    auto x = pq.top();
    pq.pop();
}
cpp

15.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. 一页速记#

最终必须牢牢记住:

  1. priority_queue 默认是大根堆,greater<T> 构造小根堆。
  2. top() 为 O(1),push/pop() 为 O(log n)。
  3. 堆只保证堆顶优先级,不保证内部全局有序。
  4. pop() 不返回值,空堆不能 top/pop。
  5. 自定义比较器方向容易与 sort 混淆,必须用小样例验证。
  6. pair 堆按字典序,{dist,node} 是 Dijkstra 的常见状态。
  7. 不支持 decrease-key,通常用重复入堆和过期状态跳过。
  8. 最大 k 个元素维护小根堆,最小 k 个维护大根堆。
  9. 相同优先级不稳定,需要时增加序号。
Comment seems to stuck. Try to refresh?✨