如何使用C++STL中的priority_queue

1、如何定义一个“priority_queue”？

priority_queue <value_type> name;

其中，value_type 是该优先队列所存储的元素类型，祝罩例如 "long long(64位整眠宿型)"，"string(字符串)"，或者一个自定义的结构体名称

还要在头文件中加上包含“priority_queue”的 "#include<queue>"

优先队列中的元素一定要定义小于号，C++中自带的类型 int,char 等已经定义好小于号了

2、同为STL的容器，priority_queue（优先队列）和 queue（队列）有共同之处，也有不同点

相同：它们都支持插入和弹出操作

不同：queue 从队尾进，队头出，不准“插队”

而 priority_queue 中的每个元素都有一个“优先级”，优先级大的先出队列

该图片来自于网络

3、1. push(x)/pop() 将x压入队列/弹出队首

其中，x的类型必须与定义时的 value_type 相一致

因为优先队列的实现是一个大根堆，所以每次 push(x)/pop() 操作的时间复杂度是 O(logn)，log以2为底，n是该优先队列中的元素个数

如图

4、2. top() 获取队首

时间复杂度 O(1)

如图

5、3. empty() 判断该优先队列是否为空

时间复杂度 O(1)

如图

6、4. size() 返回该优先队列的元素个数

时间复杂度 O(1)

如图

7、因为每次从优先队列中取出元素时总是优先级最大的那个，所以我们可以用优先队列排序，总时间 O(nlogn)，其中log以2为底，n是需要排序的元素个数

如图

8、如果 priority_queue 中的元素不是 "int"，"string" 这些已经给我们定义好小于号的类型，而是一个自定义的结构体，那该怎么办呢？

例如我们定义一个叫做 “student”的结构体，里面存储“string”类型的姓名和“int”类型的分数，我们希望把这些学生慎距凤按照分数从高到低排

如果我们直接这么定义，编译器会报错：

priority_queue <student> c;

因为我们并没有给结构体“student”定义小于号

9、这时候只需要在结构体中把“<”定义一下即可

在此之前，你需要学会 运算符重定义

10、以上就是如何使用 priority_queue （优先队列）的讲解

虽然它的内置函数不多，但我们通常会用它维护数据，熟练运用能够给我们带来很大的帮助！