不是"先来后到"，而是"谁大谁先出"——底层用二叉堆实现，永远能 O(1) 拿到当前最大（或最小）的元素。
priority_queue（优先队列）总是把最大的元素放在队首。它不是简单的"先来后到"，而是"谁大谁先出"。底层用二叉堆（binary heap）实现，插入和取出最大值都是 O(log n)，比每次排序快得多。使用前需引入 <queue> 头文件（和 queue 同一个）。
top() 是 O(1)。插入或删除元素后，二叉堆会自动"上浮"或"下沉"调整，使其重新满足这个规则，整个过程是 O(log n)——这正是 priority_queue 的底层原理，使用时不需要手写，STL 已经帮你实现好了。
默认情况下，priority_queue<int> 创建的就是一个大顶堆——也就是说，不管元素以什么顺序 push 进去，每次调用 top() 拿到的都是当前最大的那个元素。
| 1 | #include <iostream> |
| 2 | #include <queue> // 必须包含这个头文件 |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | priority_queue<int> pq; // 默认是大顶堆 |
| 8 | pq.push(3); |
| 9 | pq.push(1); |
| 10 | pq.push(4); |
| 11 | pq.push(2); |
| 12 | return 0; |
| 13 | } |
priority_queue 和 stack / queue 一样是容器适配器，没有迭代器，不能遍历。想看里面所有元素，只能一边 top() 一边 pop()，直到 empty()。| 1 | priority_queue<int> pq; |
| 2 | pq.push(3); |
| 3 | pq.push(1); |
| 4 | pq.push(4); |
| 5 | pq.push(2); |
| 6 | |
| 7 | cout << pq.top() << endl; // 输出：4——当前最大的元素 |
| 8 | pq.pop(); // 弹出 4 |
| 9 | cout << pq.top() << endl; // 输出：3——新的最大元素 |
| 10 | |
| 11 | // 逐个弹出（从大到小） |
| 12 | while (!pq.empty()) |
| 13 | { |
| 14 | cout << pq.top() << " "; // 输出：4 3 2 1 |
| 15 | pq.pop(); |
| 16 | } |
默认的 priority_queue 是大顶堆。如果想要"最小的元素优先"，有两种常用写法：
| 1 | // 写法一：用 greater（需要 vector 和 greater） |
| 2 | priority_queue<int, vector<int>, greater<int>> min_pq; |
| 3 | min_pq.push(3); |
| 4 | min_pq.push(1); |
| 5 | min_pq.push(4); |
| 6 | cout << min_pq.top() << endl; // 输出：1——当前最小的元素 |
| 7 | |
| 8 | // 写法二：竞赛常用技巧——存负数（简单省事） |
| 9 | priority_queue<int> pq; |
| 10 | pq.push(-3); // 存 -3 |
| 11 | pq.push(-1); // 存 -1 |
| 12 | pq.push(-4); // 存 -4 |
| 13 | cout << -pq.top() << endl; // 取出来再取反：1（最小的） |
| 写法 | 建议 |
|---|---|
| greater<int> | 语义清晰，推荐在正式代码中使用 |
| 存负数 | 打字更少，竞赛中很常见，但要小心负负得正的边界情况 |
greater<int> 这个比较规则定义在 <functional> 头文件里。大多数编译器的 <queue> 内部已经间接包含了它，所以上面的代码通常不加也能编译通过；但依赖这种"间接包含"并不是一个稳妥的习惯，显式加上 #include <functional> 更安全，也能让代码的依赖关系一目了然。| 1 | #include <iostream> |
| 2 | #include <queue> |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | priority_queue<int> pq; |
| 8 | pq.push(3); |
| 9 | pq.push(1); |
| 10 | pq.push(4); |
| 11 | pq.push(2); |
| 12 | |
| 13 | cout << "堆顶: " << pq.top() << endl; // 输出：4 |
| 14 | cout << "大小: " << pq.size() << endl; // 输出：4 |
| 15 | |
| 16 | // 从大到小依次弹出 |
| 17 | cout << "依次弹出: "; |
| 18 | while (!pq.empty()) |
| 19 | { |
| 20 | cout << pq.top() << " "; // 输出：4 3 2 1 |
| 21 | pq.pop(); |
| 22 | } |
| 23 | cout << endl; |
| 24 | |
| 25 | return 0; |
| 26 | } |
把本节出现过的方法按用途归类汇总，写代码时可以直接当参考卡用。
| 方法 / 写法 | 分类 | 作用 |
|---|---|---|
| pq.push(x) | 修改 | 插入元素，自动调整堆结构，O(log n) |
| pq.pop() | 修改 | 删除堆顶元素，不返回值，O(log n) |
| pq.top() | 访问 | 读取（不删除）堆顶元素，O(1) |
| pq.size() / pq.empty() | 容量 | 元素个数 / 判断是否为空 |
| priority_queue<int> | 定义 | 默认大顶堆，最大值在堆顶 |
| priority_queue<int, vector<int>, greater<int>> | 定义 | 小顶堆，最小值在堆顶 |
priority_queue 都比每次重新排序快得多。特别适合处理动态数据流的场景：数据不是一次性给好、排一次序就完事，而是不断有新数据陆续加入，你需要随时能拿到"当前"的最大值或最小值——这正是 priority_queue 能够一直保持高效（插入和取极值都是 O(log n)）而重新排序做不到的地方。