C++ 优先队列priority_queue

技术专帖

前言

       学习优先队列之前先看个单词队列 queue， 这个单词的读法很多人都能读对吧，音标是 /kjuː/ ，再看一个双端队列 deque，它的音标是 /dek/，应该有人读错了吧，反正我是没读对，刚开始看见一次错一次，现在还好了，基本能记住怎么读了，可是这些队列怎么用呢？
       队列就不用多说了，一个先进先出的经典数据结构，那么优先队列是个什么鬼，其实它就是在队列的基础上加上优先两个字，想想怎样才能优先呢？没错——排队！只有排好了队伍才会有落后和优先之分，否则一团乱糟糟的，怎么才能分出优先的，所以优先队列一定应用了排序。
       可是排序要怎样实现呢？其实排序这个底层逻辑你是不用管的，你只要把想要的数据放到优先队列里，然后取出的必定是当前状态下最优的，当然，究竟什么是最优的条件是需要你来设定的，也就是说我们需要定义排序的规则。

头文件

       优先队列 priority_queue 是队列 queue 的一个变种，头文件是#include ，使用优先队列必须要包含这个头文件。

结构定义

       优先队列的结构定义是一个模板类，需要提供三个类型参数：

1
2
3
4
5
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

       从定义可以看出，虽然要结构是三个参数，但是后两个参数带了默认值，所以针对于普通的数据类型，一般情况下指提供第1个参数就可以了，比如 priority_queue 实际上等价于 priority_queue, less>。
       这三个参数的含义分别为：数据类型，容器类型和比较函数，实际上优先队列就是维护了一个装有 T 类型元素的容器 Container，并在入队和出队时对容器内元素使用 Compare 比较函数进行了排序。
       这3个参数还要满足一定的要求，并且在使用过程中有些注意事项：
       1. 如果类型 T 和 Container 容器中元素类型不一致，那么行为未定义，所以要避免这种情况。
       2. Container 必须是序列容器，其实C++中序列容器很多的，比如std::array、std::vector、std::deque、std::list等
       3. Container 还必须要支持随机访问，并且有 front()、push_back()、pop_back() 等函数
       这样来看只有 std::vector、std::deque 满足容器条件了，而优先队列中使用的默认参数也是 std::vector。

队列排序

       一直在说优先队列里使用了排序，而常用的容器是 std::verctor，那么究竟用的是什么排序，又是在什么时候进行的排序呢？实际上这里的排序并不是我们通常拿到数据后使用的冒泡排序、快速排序等，优先队列中的排序本质上是堆排序，但是它不是每次都进行完整的堆排序，而是通过 Container 维护了一个堆结构，每次入队和出队时都进行一次堆调整，所花时间为 log(n)，所以用在数据量大的地方，速度比较快。

优先队列使用

       当我们大概了解了优先队列的原理后，可以通过使用来进一步熟悉这个结构，下面来看几个例子。

实现排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <queue>
using namespace std;
void common_sort()
{
    int source_data[10] = {3, 5, 8, 1, 10, 2, 9, 15, 13, 16};
    // 默认大根堆，实现由大到小排序
    priority_queue<int> q;
    for(auto n : source_data)
    {
        q.push(n);
    }
    while(!q.empty()) 
    {
        cout << q.top() << endl;
        q.pop();
    }
}

       priority_queue 默认构建的是一个大根堆，所以每次从头取数据得到的是一个从大到小的队列排序

1
2
3
4
5
6
7
8
9
10
11
12
pc@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o commonsort -std=c++11
pc@home-pc:/mnt/c++/datastruct$ ./commonsort
16
15
13
10
9
8
5
3
2
1

       如果是完整排序使用优先队列就有些麻烦了，还不如直接调用 std::sort 函数，但是如果只取部分数据的话，优先队列还是非常方便快速的，比如下面这个问题。

取出数组中最大的k个数

       这是一个经典的算法题，最容易想到的办法就是遍历，先找到最大的，然后排出这个数再找到最大的，这样找k次就好了，所需时间大概表示为 O(kN)。
       还有一个方法是排序，使用 std::sort 排序后，然后依次取出前 k 个数就行了，排序使用快速排序的话可以达到所需时间为 O(Nlog(N))，其实这样已经很优秀了，但是还可以通过优先队列来加速，下面来写一下代码：

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
#include <iostream>
#include <queue>
using namespace std;
void max_k_num()
{
    int source_data[10] = {3, 5, 8, 1, 10, 2, 9, 15, 13, 16};
    int k = 5;
    // 小根堆
    priority_queue<int, vector<int>, greater<int>> q;
    for(auto n : source_data)
    {
        if(q.size() == k)
        {
            if(n > q.top()) 
            {
                q.pop();
                q.push(n);
            }
        }
        else
        {
            q.push(n);
        }
    }
    while(!q.empty()) 
    {
        cout << q.top() << endl;
        q.pop();
    }
}

       这里是定义了一个小根堆，堆顶是最小值，当有新元素大于堆顶元素时，并且队列中元素等于k个，需要移除堆顶元素，然后插入新的元素，这样就能保证优先队列中始终拥有最大的k个数，运行结果如下：

1
2
3
4
5
6
7
pc@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o max_k_num -std=c++11
pc@home-pc:/mnt/c++/datastruct$ ./max_k_num
9
10
13
15
16

       因为这里控制堆的规模最大为k，所以这个算法的执行时间大概是O(Nlog(k))，绝大多数情况是优于快速排序的。

自定义结构

       使用优先队列时常常要用到自定义结构，这时候就需要自己来写比较函数了，比如输出成绩最好的三个人的信息：

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
44
45
46
47
#include <iostream>
#include <queue>
using namespace std;
struct student
{
    string name;
    int score;
};
struct cmp_custom
{
    bool operator()(student& x, student& y)
    {
        return x.score > y.score;
    }
};
void max_k_score()
{
    vector<student> stu_list = {{"Andy", 89}, {"Bella", 79}, {"Cary", 92}, {"Dick", 60}, {"Ray", 70}};
    int k = 3;
    // 小根堆
    priority_queue<student, vector<student>, cmp_custom> q;
    for(auto stu : stu_list)
    {
        if(q.size() == k)
        {
            if(stu.score > q.top().score)
            {
                q.pop();
                q.push(stu);
            }
        }
        else
        {
            q.push(stu);
        }
    }
    while(!q.empty())
    {
        cout << q.top().name << ":" << q.top().score << endl;
        q.pop();
    }
}

       输出结果如下，每个人的名字后面跟着分数，结果是分数最大的3个人的信息：

1
2
3
4
5
pc@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o max_k_score -std=c++11
pc@home-pc:/mnt/c++/datastruct$ ./max_k_score
Bella:79
Andy:89
Cary:92

       自定义比较函数的另一种写法
       看到上个例子中自定义比较函数的写法比较怪，一般我们在排序时定义的比较函数使用lambda表达式就可以，而这里是不能直接这样写的，需要多转化一步，写成下面这种形式：

1
2
auto cmp = [](student& x, student& y) { return x.score > y.score; };
priority_queue<student, vector<student>, decltype(cmp)> q(cmp);

       虽然看起来还是有点怪，但总比下面这样要好看的多：

1
2
3
4
5
6
7
8
struct cmp_custom
{
    bool operator()(student& x, student& y)
    {
        return x.score > y.score;
    }
};
priority_queue<student, vector<student>, cmp_custom> q;

常用函数

       优先队列的常用函数与队列类似，常用的有以下这些，如果想了解详细的用法，请戳在线文档

函数名 含义
top 访问队列的头部元素
empty 判断优先队列内是否有元素
size 返回优先队列内元素个数
push 向优先队列中插入元素
emplace 在优先队列中构造元素
pop 从优先队列头部弹出元素
swap 与其他容器交换元素

总结

       1. 优先队列在一些需要部分排序的场景可以加快访问速度，降低时间复杂度。
       2. 优先队列加速所付出的代价就是构建堆结构所需的内存，时间和空间总是一对矛盾共同体。
       3. 以自定义结构作为元素的优先队列需要单独编写比较函数，可以使用lambda表达式，并用 decltype(cmp) 推导类型。
       4. 需要注意的是这里的优先队列定义，第三个参数的需要的是比较函数的参数类型，而不是比较函数，区分与 std::sort 的不同。

本文标题:C++ 优先队列priority_queue

文章作者:Greedysky

发布时间:2021年08月29日 - 10时26分

最后更新:2022年11月28日 - 16时52分

原始链接:http://greedysky.github.io/2021/08/29/C++优先队列priority_queue/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 前言
  2. 2. 头文件
  3. 3. 结构定义
  4. 4. 队列排序
  5. 5. 优先队列使用
  6. 6. 实现排序
  7. 7. 取出数组中最大的k个数
  8. 8. 自定义结构
  9. 9. 常用函数
  10. 10. 总结