STL库--priority_queue
目录
priority_queue又称为优先队列，其底层是用堆来进行实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。例如在队列有如下元素，且定义好了优先级：
桃子（优先级3）
梨子（优先级4）
苹果（优先级1）那么出队的顺序为梨子（4）、桃子（3）、苹果（1）
当然，可以在任何时候往优先队列里面加入元素，而优先队列底层的数据结构堆会随时调整结构，使得每次的队首元素都是优先级最大的。关于这里的优先级则是规定出来的。
priority_queue定义
其定义的写法和其他STL容器相同，typename可以是任意基本数据类型或容器
prioroty_queue<typename> name;prority_queue容器内元素的访问
和队列不一样的是，优先队列没有front()函数与back()函数，而只能通过top()函数来访问队首元素，也就是优先级最高的元素。
#include<stdio.h>
#include<queue>
using namespace std;
int main(){
priority_queue<int> q;
q.push(3);
q.push(4);
q.push(1);
printf("%d\n",q.top());
return 0;
}输出结果
4priority_queue()常用函数实例解析
（1）push()
push(x)将令x入队，时间复杂度为，其中N为当前优先队列中的元素个数
（2）top()
top()可以获得队首元素，时间复杂度为
（3）pop()
pop()令队首元素出队，时间复杂度为，其中N为当前优先队列中的元素个数。
#include<stdio.h>
#include<queue>
using namespace std;
int main(){
priority_queue<int> q;
q.push(3);
q.push(4);
q.push(1);
printf("%d\n",q.top());
q.pop();
printf("%d\n",q.top());
return 0;
}输出结果
4
3（4）empty()
empty()检测优先队列是否为空，返回true则空，返回false则非空，时间复杂度为
#include<stdio.h>
#include<queue>
using namespace std;
int main(){
priority_queue<int> q;
if(q.empty()==true){
printf("Empty\n");
}
else{
printf("Not Empty\n");
}
q.push(1);
if(q.empty()==true){
printf("Empty\n");
}
else{
printf("Not Empty\n");
}
return 0;
}（5）size()
size()返回优先队列内元素的个数，时间复杂度为
#include<stdio.h>
#include<queue>
using namespace std;
int main(){
priority_queue<int> q;
q.push(3);
q.push(4);
q.push(1);
printf("%d\n",q.size());
return 0;
}priority_queue内元素优先级的设置
如何定义优先队列内元素的优先级是运用好优先队列的关键，下面分别介绍基本数据类型与结构体类型的优先级设置方法。
（1）基本数据类型的优先级设置
此处指的基本数据类型就是int型，double型，char型等可以直接使用的数据类型，优先队列对它们的优先级设置一般是数字大的优先级越高，因此队首元素就是优先队列内的元素最大的那个（如果char型，则是字典序最大的）。对基本数据类型来说，下面两种优先队列的定义是等价的（以int型为例）
prioroty_queue<int> q;
priority_queue<int,vector<int>,less<int> > q;可以发现，第二种定义方式的尖括号多出了两个参数：一个是vector<int>，另一个是less<int>。其中vector<int>填写的是来承载底层数据结构堆的容器，如果第一个参数是double型或char型，则此处只需要填写vector<double>或vector<char>；而第三个参数less<int>则是对第一个参数的比较类，less<int>表示数字大的优先级越大，而greater<int>表示数字小的优先级越大。
因此，如果想让优先队列总是把最小的元素放在队首，只需进行如下定义：
priority_queue<int,vector<int>,greater<int> > q;#include<stdio.h>
#include<queue>
using namespace std;
int main(){
priority_queue<int,vector<int>,greater<int> > q;
q.push(3);
q.push(4);
q.push(1);
printf("%d\n",q.top());
return 0;
}输出结果
1事实上，即便是基本数据类型，也可以使用下面的结构体的优先级设置方法，只不过第三个参数的写法不太一样。
（2）结构体的优先级设置
可以举一个水果的例子，对水果的价格和名称建立一个结构体
struct fruit{
string name;
int price;
};现在希望按水果的价格高的为优先级高，就需要重载小于号"<"。重载是指对已有的运算符进行重新定义，也就是说，可以改变小于号的功能，写法如下：
struct fruit{
string name;
int price;
friend bool operator < (fruit f1,fruit f2){
return f1.price < f2.price;
}
};可以看到，fruit结构体增加了一个函数，其中”friend"为友元，后面的”bool operator < (fruit f1,fruit f2)"对fruit类型的操作符“<"进行了重载（重载大于号会编译错误，因为从数学上来说只需要重载小于号，即f1>f2等价于判断f2<f1，而f1==f2等价于判断!(f1<f2)&&!(f2<f1)，函数内部为"return f1.price<f2.price"，因此重载后小于号还是小于号的作用。此时就可以直接定义fruit类型的优先队列，其内部就是以价格高的水果为优先级高。
priority_queue<fruit> q;同理，如果想要以价格低的水果为优先级高，那么只需要把return中的小于号改为大于号即可。
struct fruit{
string name;
int price;
friend bool operator < (fruit f1,fruit f2){
return f1.price > f2.price;
}
};完整代码如下：
#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{
string name;
int price;
friend bool operator < (fruit f1,fruit f2){
return f1.price > f2.price;
}
}f1,f2,f3;
int main(){
priority_queue<fruit> q;
f1.name="桃子";
f1.price=3;
f2.name="梨子";
f2.price=4;
f3.name="苹果";
f3.price=1;
q.push(f1);
q.push(f2);
q.push(f3);
cout<<q.top().name<<" "<<q.top().price<<endl;
return 0;
}输出结果
苹果 1此处对小于号的重载与排序函数sort中的cmp函数有些相似，它们的参数都是两个变量，函数内部都是return了true或者false。事实上，这两者的作用确实是类似的，只不过效果看上去似乎是相反的。在排序中，如果return f1.price>f2.price，那么则是按照价格从高到低排序，但是在优先队列中却是把价格低的放在队首。原因在于，优先队列本身静默的规则就是优先级高的放在队首，因此把小于号重载为大于号的功能时只是把这个规则反向了一下。只需要记住，优先队列的这个函数与sort中的cmp函数的效果是相反的。
或者也可以把结构体定义在外面，只需要把friend去掉，把小于号改成一对小括号，然后把重载的函数写在结构体外面，同时将其用struct包装起来。
struct cmp{
bool operator () (fruit f1,fruit f2){
return f1.price > f2.price;
}
};在这种情况下需要用之前讲解的第二种定义方式来定义优先队列
priority_queue<fruit,vector<fruit>,cmp> q;完整代码如下：
#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{
string name;
int price;
}f1,f2,f3;
struct cmp{
bool operator () (fruit f1,fruit f2){
return f1.price > f2.price;
}
};
int main(){
priority_queue<fruit,vector<fruit>,cmp> q;
f1.name="桃子";
f1.price=3;
f2.name="梨子";
f2.price=4;
f3.name="苹果";
f3.price=1;
q.push(f1);
q.push(f2);
q.push(f3);
cout<<q.top().name<<" "<<q.top().price<<endl;
return 0;
}当然即便是基本数据类型或者其他STL容器，也可以通过同样的方式来定义优先级。
最后指出，如果结构体内的数据较为庞大（例如出现了字符串或者数组），建议使用引用来提高效率，此时比较类的参数需要加上"const"和"&"
friend bool operator < (const fruit &f1,const fruit &f2){
return f1.price > f2.price;
}
bool operator() (const fruit &f1,const fruit &f2){
return f1.price > f2.price;
}priority_queue的常见用途
priority_queue可以解决一些贪心问题，也可以对Dijkstra算法进行优化。
但是注意在使用tiop()函数前，必须用empty()判断优先队列是否为空。
原文地址：https://blog.csdn.net/m0_72674633/article/details/139297518
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！