# 优先队列priority_queue
#include <queue>
提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。
# 1. 常用方法
# 构造
priority_queue<类型，容器，比较器>pque
类型：要储存的数据类型
容器：储存数据的底层容器，默认为 vector<类型>，竞赛中保持默认即可
比较器：比较大小使用的比较器，默认为
less<类型>，可自定义
//储存int的大顶堆
priority_queue<int> pquel; // 默认大顶堆
priority_queue<int, vector<int>, greater<int>> pque2;// 储存int的小顶堆，greater<int>控制
1
2
3
2
3
对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法(重载小括号运算符/ambda 表达式)，在此就不展开讲了。如 果想要了解，可以查阅 cppreference (opens new window) 中的代码示例。
# 其他
| 作用 | 用法 | 示例 |
|---|---|---|
| 进堆 | .push(元素) | que.push(1); |
| 出堆 | .pop() | que.pop(); |
| 取堆顶 | .top() | int a= que.top(); |
| 查看大小/判空 | 略 | 略 |
进出队复杂度 ，取堆顶$ O(1)$.
# 2. 适用情形
持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列里取出大小最大/最小的元素，元素数量n，插入操作数量k
- 每次插入后进行快速排序：
- 使用优先队列维护：
# 3. 注意事项
# 仅堆顶可读
只可访问堆顶，其他元素都无法读取到。下面是错误用法：
cout << pque[1] << endl;
1
# 所有元素不可写
堆中所有元素是不可修改的。下面是错误用法：
pque[1] = 2;
pque.top() = 1;
1
2
2
如果恰好要修改的是堆顶元素，则可以通过以下完成：
int tp = pque.top(); //先将堆顶取出来，存在tp里
pque.pop(); //再弹出堆顶
pque.push(tp+1); //最后将修改的tp再压入堆里，此时不一定再是堆顶，因为 只有大顶堆和小顶堆
1
2
3
2
3