csp信奥赛C++标准模板库STL（10）：priority_queue的使用详解
一、什么是优先队列？
priority_queue是一种容器适配器，它提供了一种可以快速访问“最大”或“最小”元素的队列。它的底层通常由堆（Heap）数据结构实现（默认是大顶堆），因此插入和删除元素的时间复杂度都是O(log n)，访问堆顶元素是O(1)。
核心思想：普通的队列是“先进先出”，而优先队列是“优先级高的先出”。这个“优先级”可以是你定义的任何比较规则。
二、基本用法（头文件与声明）
#include<queue>// 注意：不是#include <priority_queue>usingnamespacestd;// 最常见的声明方式：// 1. 默认大顶堆 (降序队列，最大的元素在队首)priority_queue<int>pq1;// 2. 小顶堆 (升序队列，最小的元素在队首)priority_queue<int,vector<int>,greater<int>>pq2;// 记住这个写法！参数解释：
int：队列中存储的数据类型。vector<int>：用于承载堆的底层容器，必须是随机访问容器（如vector,deque），默认为vector。greater<int>：是一个仿函数（函数对象），用于决定比较规则。greater意味着“更大”的优先级反而更低，所以成了小顶堆。默认是less<int>，即“更小”的优先级更低，所以是大顶堆。
三、核心操作
假设我们声明了一个默认的大顶堆priority_queue<int> pq：
| 操作 | 代码 | 功能描述 | 时间复杂度 |
|---|---|---|---|
| 插入元素 | pq.push(x) | 将元素x插入优先队列 | O(log n) |
| 访问堆顶 | pq.top() | 返回优先级最高的元素（大顶堆即最大值） | O(1) |
| 弹出堆顶 | pq.pop() | 删除优先级最高的元素（不返回值） | O(log n) |
| 队列大小 | pq.size() | 返回队列中元素个数 | O(1) |
| 判断空 | pq.empty() | 队列为空返回true，否则false | O(1) |
重要注意事项：
- 没有
pq.front()或pq.back()！只有pq.top()用来访问堆顶。 pq.pop()只删除，不返回。你需要先用pq.top()获取值，再pq.pop()删除。- 清空队列：
while (!pq.empty()) pq.pop();或直接重新构造pq = priority_queue<int>();。
四、在竞赛中的关键应用技巧
1. 实现小顶堆
想要一个“从小到大”出队的队列（例如解决 Dijkstra 最短路算法），必须完整声明：
priority_queue<int,vector<int>,greater<int>>minHeap;minHeap.push(3);minHeap.push(1);minHeap.push(4);cout<<minHeap.top();// 输出 12. 存储自定义类型（结构体）
你需要定义该类型的比较规则。有两种常用方法：
方法A：重载结构体的operator<（推荐，更简洁）
注意：在priority_queue中，即使默认是less，它也是用operator<来比较。但它的逻辑是：如果a < b为真，则认为a的优先级低于b，b应该在前面。所以对于大顶堆，我们希望大的在前面，就应该定义“当a.val < b.val时，a的优先级低于b”，这恰恰就是默认的less行为。因此，如果你想用priority_queue<Node> pq这种简洁形式定义大顶堆，需要重载<，并且逻辑与你想要的“优先级”相反。
structNode{intx,y;// 方法A1： 希望按 x 值大的优先级高（大顶堆）booloperator<(constNode&other)const{returnx<other.x;// 注意：这里写 `<`，但含义是“当前x小于别的x，则优先级低”}// 方法A2： 希望按 x 值小的优先级高（小顶堆）// bool operator < (const Node& other) const {// return x > other.x; // 这里写 `>`，实现了反向逻辑// }};priority_queue<Node>pq;// 将使用方法A1里定义的operator<方法B：自定义比较类/函数
更灵活，优先级逻辑更直观。
structNode{intx,y;};// 比较类（仿函数）structcmp{// 希望 Node 按 x 大的优先级高（大顶堆）booloperator()(constNode&a,constNode&b){returna.x<b.x;// 如果 a.x < b.x，则 a 的优先级低于 b}// 如果希望按 x 小的优先级高（小顶堆），则写 return a.x > b.x;};// 声明时传入比较类priority_queue<Node,vector<Node>,cmp>pq;// 也可以使用 lambda 表达式 (C++11以上，注意语法稍复杂)autocomp=[](constNode&a,constNode&b){returna.x<b.x;};priority_queue<Node,vector<Node>,decltype(comp)>pq_lambda(comp);3. 典型解题模式与例题
优先队列常用于贪心算法和维护动态极值的场景。
模式1：合并果子 / Huffman编码问题
题目：每次选择权值最小的两堆果子合并，代价为两堆之和，求最小总代价。
解法：使用小顶堆，每次弹出两个最小的，计算和，再将和压入堆，直到只剩一堆。
priority_queue<int,vector<int>,greater<int>>minHeap;// 将所有果子重量放入minHeapwhile(minHeap.size()>1){inta=minHeap.top();minHeap.pop();intb=minHeap.top();minHeap.pop();intcost=a+b;ans+=cost;minHeap.push(cost);}模式2：维护序列的前K大（或前K小）元素
题目：求数据流的中位数，或输出每次操作后第K大的数。
解法：使用两个堆（对顶堆）。例如求中位数：
- 大顶堆
left存较小的一半数据。- 小顶堆
right存较大的一半数据。- 保持
left.size() == right.size()或left.size() == right.size() + 1，则中位数就在堆顶。
模式3：Dijkstra算法求最短路
用小顶堆 (
pair<int, int>， 第一维是距离，第二维是节点编号) 来替代普通队列，可以快速取出当前未确定距离且距离最小的节点，将复杂度优化到 O((V+E) log V)。
usingPII=pair<int,int>;// (距离， 点)priority_queue<PII,vector<PII>,greater<PII>>pq;// 小顶堆，按距离排序vector<int>dist(n+1,INF);dist[start]=0;pq.push({0,start});while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(d!=dist[u])continue;// 过时的信息，跳过for(auto&[v,w]:graph[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;pq.push({dist[v],v});}}}模式4：带“反悔”的贪心
某些问题中，我们做出的选择在未来可能需要撤销（反悔），优先队列可以很好地维护当前的最优选择和备选方案。
五、与set/multiset的对比
| 特性 | priority_queue | set/multiset(平衡树) |
|---|---|---|
| 访问最大/最小元素 | O(1) | O(log n) |
| 插入元素 | O(log n) | O(log n) |
| 删除指定元素 | 不支持(只能删堆顶) | O(log n) |
| 查找任意元素 | 不支持 | O(log n) |
| 有序遍历 | 不支持 | 支持 |
| 内存开销 | 较小 | 较大 |
选择策略：
- 如果你只需要不断地访问和移除当前最大/最小值，用
priority_queue。 - 如果你需要频繁查找、删除任意值，或需要有序数据，用
set/multiset。
六、总结与要点
- 核心：
priority_queue是堆，用于 O(log n) 插入、O(1) 访问最值、O(log n) 删除最值。 - 声明：默认为大顶堆 (
less)。小顶堆必须用priority_queue<T, vector<T>, greater<T>>。 - 操作：只有
push(),pop(),top(),empty(),size()。 - 自定义类型：必须提供比较规则。重载
operator<时，逻辑要与想要的优先级相反；或自定义比较类，逻辑更直观。 - 竞赛应用：牢记几个模式——合并果子（小顶堆贪心）、Dijkstra（小顶堆优化）、对顶堆（维护第K大/中位数）、反悔贪心。
- 注意事项：它不提供迭代器，无法遍历；无法删除特定元素（除非自己实现一个“延迟删除”技术）。
掌握好priority_queue，能让你在解决涉及动态极值、贪心策略的竞赛题目时事半功倍！多加练习，理解其“优先级”的本质。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
