1 介绍

包含于头文件<queue>中，它是STL的一个容器适配器（因为没有自己的数据结构，依赖于其他底层数据结构）；

template<
    class T,
    class Container = std::vector<T>,//默认底层数据结构为vector
    class Compare = std::less<typename Container::value_type>//默认算子为less
> class priority_queue;

逻辑上，是一个堆；
物理上，是一个vector或deque等（看你选择的那个底层数据结构）
特点：
- 新元素进堆，自动按优先级从高到低排序；每次出堆，总是堆顶元素（优先级最高的元素）；
- 优先队列的出队和入队的时间复杂度均为O(logn)，即最多达到树（堆）的深度；
常用基本函数：（v为底层数据结构）
- size，返回容纳的元素数
- empty，检查底层容器是否为空
- top，访问栈顶（队头）（优先级最高）元素？等价于调用v.front()
- push，插入元素，并对底层容器排序
- emplace，原位构造元素并排序底层容器
- pop，删除队首(队头)元素？等价于调用std::pop_heap(v.begin(), v.end(), comp); v.pop_back();
- swap，与另一个priority_queue交换内容

2 坑点：决定优先级的算子

优先队列的算子关于传入的算子，是用来定义优先级别的，但是他的用法与sort恰恰相反；

vector<int> v{5,4,3,2,1};
sort(v.begin(),v.end(),[](int a,int b){return a<b;})//那么vector中元素会从小到大排列,即1，2，3，4，5
//-------------------
auto cmp = [](int a,int b){return a<b};
std::priority_queue<int, std::vector<int>, decltype(cmp) > q2(cmp);
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5)
//q中元素顺序为5,4,3,2,1
//优先级顺序与内存中元素存储顺序相同：5 -> 4 -> 3 -> 2 -> 1

结论：算子排序元素的顺序与元素优先级的顺序相反；元素优先级顺序与内存中存储顺序一致

3 示例代码

#include <queue>
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>

//g++ -o priority_queue priority_queue.cc -std=c++17
template<typename T> 
void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << std::endl;
}

class Data
{
public:
	Data(int a,double b):int_(a),double_(b){}
	int int_;
	double double_;
};
std::ostream& operator<<(std::ostream &out,Data& d)
{
	out << d.int_ << " " << d.double_ << std::endl;
	return out;
}

int main() {
    std::priority_queue<int> q;//默认大顶堆，内存中的序列是9,8,7,6,5,4,3,2,1,0
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
    print_queue(q);

    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;//小顶堆,内存中的序列是0,1,2,3,4,5,6,7,8,9
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
    print_queue(q2);

	Data d1(3,2.43);
	Data d2(3,1.43);
    auto cmp = [](const Data& d1,const Data& d2){return d1.int_==d2.int_?d1.double_>d2.double_:d1.int_>d2.int_;};//自定义算子
    std::priority_queue<Data, std::vector<Data>, decltype(cmp)> q3(cmp);
    q3.push(d1);
	q3.push(d2);
	Data dd =q3.top();
	std::cout<<dd;

	return 0;
}
/*输出：
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
3 1.43
*/