# 优先队列
优先队列（`priority_queue`）是 C++ 将二叉堆封装好的 STL 容器，能够快速地支持：
- 插入元素
- 删除优先级最高（堆顶）的元素
- 访问优先级最高（堆顶）的元素
优先队列的使用和时间常数比 `set` 要小，因此应尽量使用优先队列替代 `set`。
## 定义
### 头文件
```cpp
#include <queue>
```
### 定义
定义时需要三个参数：数据类型为 `TypeName`，底层容器为 `Container`，比较器函数对象为 `Compare`。当不指定 `Container` 和 `Compare` 时，默认底层容器为 `vector<TypeName>`，默认比较器为 `less<TypeName>`，此时优先级最高的元素为**最大**的元素。
```cpp
#include <queue>
#include <vector>
#include <functional>
priority_queue<TypeName, Container, Compare> pq;
priority_queue<int> pq1; // 默认为大根堆
// 小根堆，需要引入头文件 <functional>
priority_queue<int, vector<int>, greater<int>> pq3;
using pii = pair<int, int>;
priority_queue<pii> pq4;
priority_queue<pii, vector<pii>, greater<pii>> pq5;
```
## 成员函数
$O(1)$ 时间复杂度：
* `top()`：访问优先级最高的元素（优先队列不能为空，否则 `RE`）
* `empty()`：判断容器是否为空
* `size()`：查询元素数量
* `a.swap(b)`：交换两个优先队列容器 `a` 和 `b` 的内容 ，要求 `a` 和 `b` 定义时的三个模板参数均相同；等同于 `swap(a, b)`。
$O(\log n)$ 时间复杂度：
* `push(x)`：插入元素
* `pop()`：删除优先级最高的元素（优先队列不能为空，否则 `RE`）
* `emplace(x)`：原地构造元素并插入，没有移动或拷贝
没有 `clear()` 方法。若要实现清空容器，可以在函数内局部定义容器然后退出函数时析构，或者不断 `pop()` 直至容器为空，或者与一个临时的空容器进行交换。
```cpp
priority_queue<int> pq1;
void A1() {
priority_queue<int> pq2;
}
void Clear() {
for (; pq.size(); pq.pop()) {
}
priority_queue<int>().swap(pq);
}
```
关于原地构造 `emplace()`，请参考[[原地构造]]。
## 自定义比较器
对于结构体类型，我们需要定义其比较规则才能用优先队列维护该类型元素。本处结构体定义如下：
```cpp
struct Node {
int x, id;
};
```
阅读本处请参考[[自定义比较器]]。
请注意，比较器规则为**小元素靠前**，而优先队列中的优先级最高的元素为比较规则下**最大**的元素。
### 方法 1：functor
```cpp
// 最一般的写法
struct cmp {
bool operator()(const Node &i, const Node &j) const { // 函数尾的 const 修饰符表示该函数不能对所在类的成员进行修改
return i.x < j.x;
}
};
priority_queue<Node, vector<Node>, cmp> pq; // 定义了一个 x 为关键字的大根堆
```
### 方法 2：重载 `<` 运算符
```cpp
struct Node {
int x, id;
bool operator<(const Node &i) const {
return x > i.x;
}
};
priority_queue<Node> pq; // 定义了一个 x 为关键字的小根堆
```
### 方法 3：lambda 表达式
```cpp
auto cmp = [](const Node &i, const Node &j) {
return i.x < j.x;
};
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp); // x 为关键字的大根堆
```
### 例子 1
```cpp
struct cmp{
bool operator()(int i, int j) {
return i > j;
}
};
priority_queue<int> pq1; // 默认为大根堆
priority_queue<int, vector<int>, cmp> pq2; // 特别注意比较器的实现，跟 sort 比较器反着来
pq1.push(1);
pq1.push(2);
cout << pq1.top() << '\n'; // 2
pq1.pop();
cout << pq1.top() << '\n'; // 1
pq2.push(1);
pq2.push(2);
cout << pq2.top() << '\n'; // 1
pq2.pop();
cout << pq2.top() << '\n'; // 2
```
### 例子 2
```cpp
struct Student {
int a, b, c; // 语数外
};
struct cmp {
bool operator()(const Student &i, const Student &j) const {
if (i.a != j.a) {
return i.a < j.a;
}
if (i.b != j.b) {
return i.b < j.b;
}
return i.c < j.c;
}
};
priority_queue<Student, vector<Student>, cmp> pq; // 按语数外从高到低排
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
pq.push({100, 100, 90});
pq.push({100, 100, 100});
pq.push({100, 90, 100});
pq.push({90, 100, 100});
while (!pq.empty()) {
Student x = pq.top();
pq.pop();
cout << x.a << ' ' << x.b << ' ' << x.c << '\n';
}
return 0;
}
```