目录

C++ STL priority_queue使用技巧

简介

定义在头文件<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

总结

  1. 默认是大根堆,大的数在顶上

  2. 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
    }
    
  3. 自定义比较函数

    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;
    }
    
  4. 自定义比较函数写法priority_queue<T, vector<T>, decltype(&cmp)> q(cmp);