C++中优先队列priority_queue的基础用法

发表于 | 更新于 | 分类于 |
热度 ℃   |   字数统计: 2,378(字)   |   阅读时长: 9(分) |

前言

学习优先队列之前先看个单词队列 queue， 这个单词的读法很多人都能读对吧，音标是 /kjuː/ ，再看一个双端队列 deque，它的音标是 /dek/，应该有人读错了吧，反正我是没读对，刚开始看见一次错一次，现在还好了，基本能记住怎么读了，可是这些队列怎么用呢？

队列就不用多说了，一个先进先出的经典数据结构，那么优先队列是个什么鬼，其实它就是在队列的基础上加上优先两个字，想想怎样才能优先呢？没错——排队！只有排好了队伍才会有落后和优先之分，否则一团乱糟糟的，怎么才能分出优先的，所以优先队列一定应用了排序。

可是排序要怎样实现呢？其实排序这个底层逻辑你是不用管的，你只要把想要的数据放到优先队列里，然后取出的必定是当前状态下最优的，当然，究竟什么是最优的条件是需要你来设定的，也就是说我们需要定义排序的规则。

头文件

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

结构定义

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

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<int> 实际上等价于 priority_queue<int, vector<int>, less<int>>。

这三个参数的含义分别为：数据类型，容器类型和比较函数，实际上优先队列就是维护了一个装有 T 类型元素的容器 Container，并在入队和出队时对容器内元素使用 Compare 比较函数进行了排序。

这3个参数还要满足一定的要求，并且在使用过程中有些注意事项：

  • 如果类型 T 和 Container 容器中元素类型不一致，那么行为未定义，所以要避免这种情况。
  • Container 必须是序列容器，其实C++中序列容器很多的，比如std::array、std::vector、std::deque、std::list等
  • 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
#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<int> 默认构建的是一个大根堆，所以每次从头取数据得到的是一个从大到小的队列排序

1
2
3
4
5
6
7
8
9
10
11
12
albert@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o commonsort -std=c++11
albert@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
#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
albert@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o max_k_num -std=c++11
albert@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
#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
albert@home-pc:/mnt/c++/datastruct$ g++ priorityqueue.cpp -o max_k_score -std=c++11
albert@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
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 与其他容器交换元素

总结

  • 优先队列在一些需要部分排序的场景可以加快访问速度，降低时间复杂度
  • 优先队列加速所付出的代价就是构建堆结构所需的内存，时间和空间总是一对矛盾共同体
  • 以自定义结构作为元素的优先队列需要单独编写比较函数，可以使用lambda表达式，并用 decltype(cmp) 推导类型
  • 需要注意的是这里的优先队列定义，第三个参数的需要的是比较函数的参数类型，而不是比较函数，区分与 std::sort 的不同
==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

人在比较中奋进，同在比较中消亡，起初面临差距时会奋起直追，但是当努力过后发现距离反而越来越远时，便会麻木懈怠，曾经的努力没有用吗？我觉得不是，努力过不一定会成功，但是努力的过程已经印在了骨子里，这本身就是生活的一部分。你可以选择这条艰苦的路，同样也可以选择跳过，至于跳过时错失了什么，谁又知道呢？毕竟人生无法再来过，重新读档只发生在游戏世界中~

2020-9-12 17:06:10

Albert Shi wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客