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

前言

学习优先队列之前先看个单词队列 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个参数还要满足一定的要求,并且在使用过程中有些注意事项:

  • 如果类型 TContainer 容器中元素类型不一致,那么行为未定义,所以要避免这种情况。
  • Container 必须是序列容器,其实C++中序列容器很多的,比如std::arraystd::vectorstd::dequestd::list
  • Container 还必须要支持随机访问,并且有 front()push_back()pop_back() 等函数

这样来看只有 std::vectorstd::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
欢迎您扫一扫上面的微信公众号,订阅我的博客