简介
定义在头文件<queue>中
priority_queue<Type, Container, Functional>
1
2
3
4
5
| template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
class priority_queue;
|
常用操作：
top()
empty()
size()
push()
emplace()
pop()
大、小根堆
对于单一数值类型如int类型：
1
2
3
4
5
6
7
8
9
| #include <functional> // 因为用到了greater<int>和less<int>
#include <queue>
// 小顶堆
priority_queue<int, vector<int>, greater<int>> q;
// 大顶堆
priority_queue<int, vector<int>, less<int>> q;
// 默认大顶堆
priority_queue<int> q;
|
对于自定义类型，需要指明容器，以及优先级规则，如pair<int, int>类别
1
2
| typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, decltype(&cmp)> q(cmp); // cmp为一个比较函数
|
Example code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
// 假设按照pair的第二个数来进行排序，这样说明是按第二个数升序，是小根堆，没啥好说的，记住就行了。
bool cmp(const PII& p1, const PII& p2) {
return p1.second > p2.second;
}
int main() {
vector<PII> pairs = {{1, 4}, {2, 9}, {5, 3}, {4, 1}, {3, 6}};
priority_queue<PII, vector<PII>, decltype(&cmp)> q(cmp); // 声明了一个pair的根据第二个数比较的小根堆
for (auto p : pairs) {
q.push(p);
}
while (q.size()) {
cout << q.top().first << q.top().second << endl;
}
return 0;
}
|
output:
1
2
3
4
5
| 4 1
5 3
1 4
3 6
2 9
|
综合案例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <functional>
#include <queue>
#include <vector>
#include <iostream>
template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
while(!q.empty()) {
std::cout << q.top() << ' ';
q.pop();
}
std::cout << '\n';
}
int main() {
const auto data = {1,8,5,6,3,4,0,9,7,2};
// 默认的是大根堆
// 输出结果: 9 8 7 6 5 4 3 2 1 0
std::priority_queue<int> q;
for(int n : data)
q.push(n);
print_queue(q);
// 声明了一个小根堆
// 输出结果：0 1 2 3 4 5 6 7 8 9
std::priority_queue<int, std::vector<int>, std::greater<int>>
q2(data.begin(), data.end());
print_queue(q2);
// 利用lambda表达式来写比较函数
// 按给定规则，小于号说明是个大根堆，根据两个数与1异或之后的大小。
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
for(int n : data)
q3.push(n);
print_queue(q3);
}
|
output:
1
2
3
| 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
8 9 6 7 4 5 2 3 0 1
|
总结
默认是大根堆，大的数在顶上
greater<int>是小根堆，less<int>是大根堆。
1
2
3
4
5
6
7
8
9
10
| // greater:
constexpr bool operator()(const T &lhs, const T &rhs) const
{
return lhs > rhs; // assumes that the implementation uses a flat address space
}
// less:
constexpr bool operator()(const T &lhs, const T &rhs) const
{
return lhs < rhs; // assumes that the implementation uses a flat address space
}
|
自定义比较函数
1
2
3
4
5
6
7
8
9
| // 小根堆
bool cmp(const T& t1, const T& t2) {
t1 > t2;
}
// 大根堆
bool cmp(const T& t1, const T& t2) {
t1 < t2;
}
|
自定义比较函数写法priority_queue<T, vector<T>, decltype(&cmp)> q(cmp);