C++中的优先队列

2021-04-07

C++优先队列默认的是大根堆。

优先队列的特点：

首先优先队列延续了队列的内涵，从队尾入队，从队头出队。但是入队出队过程并不是传统的FIFO方式，而是在内部给成员确定了优先级，每个元素出队时按照优先级最大或者最小进行出队。优先队列的这种数据结构就是最大堆或者最小堆。因此，如果需要使用最大堆或者最小堆的问题，可以直接使用优先队列来解决。

元素入队时先排在堆的最后一个位置，然后进行上浮；元素出队时取出根节点元素，将最后一个节点放入根节点，然后进行下浮。对于优先队列这种由STL实现的数据结构来说，我们已经不需要自己去实现这种模板的功能，只需要将模板具体化就能方便使用。

优先队列的使用：

1.#include包含队列的头文件注意有个万能头文件，实现需要去判断下oj平台是否支持，#include <bits/stdc++.h>

2.优先队列的构造
template<_Tp, _Sequence = vector<_Tp>, _Compare = less<value_type>>
优先队列使用就是模板实例化，具体来说需要指定三个参数，_Tp, _Sequence和_Sequence三部分。其中第一个是容器内部具体要保存的数据类型，比如int，float，pair或者tuple，_Sequence代表底层容器的具体类型，如vector、deque等，cpp默认的容器是vecctor，而_Compare函数则是用户定义的比较函数，决定了比较的元素和比较的规则，cpp默认是按照_Tp中的第一个元素进行比较，并且默认是大根堆。
例如

1	priority_queue<tuple<float, int, int>>q; //默认使用第一个元素比较，产生大根堆

等价于

using eletype = tuple<float, int, int>;
// 注意这里小于号对应大根堆，大于号对应小根堆
auto cmp = [](eletype a, eletype b) {return get<0>(a) < get<0>(b);}; 
priority_queue<eletype, vector<eletype>, decltype(cmp)>q(cmp);

注意几点：

cpp中定义lambda表达式是看不到lambda字眼的，不要和python搞混了；
cpp定义lambda表达式结尾的大括号处需要添加分号；
cpp中tuple不能直接使用下标访问，需要使用get(tuple)的方式来访问；
cpp中优先队列需要在模板的第三个参数给出比较函数类型，同时需要在构造优先队列对象时给构造函数传入具体的比较函数。
对于tuple的具体解包，可以使用
1
2
tuple<double, int, int>element{1.12, 2, 3}; //用法和vector初始化很类似
auto [x, y, z] = element;

3.优先队列的操作

出队：pop函数，返回类型void;
入队：push函数，需要先构建一个临时变量，再调用复制构造函数到队列的尾部；emplace函数，直接原地构造，传入对象构造函数所需参数；
访问队头元素：top函数；
队列元素数量：size函数
队列是否为空：empty函数
交换内容：swap函数， queue1.swap(queue2)，将具有相同数据类型和大小的队列元素交换。

cpp pair类型访问

1
2
3

pair<float, int>a{1.0, 2};
a.first;
a.second;