priority_queue
priority_queue 优先队列,其底层是用堆来实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。
在优先队列中,没有 front() 函数与 back() 函数,而只能通过 top() 函数来访问队首元素(也可称为堆顶元素),也就是优先级最高的元素。
一、基本数据类型的优先级设置
- 此处指的基本数据类型就是 int 型,double 型,char 型等可以直接使用的数据类型,优先队列对他们的优先级设置一般是数字大的优先级高,因此队首元素就是优先队列内元素最大的那个(如果是 char 型,则是字典序最大的)。
//下面两种优先队列的定义是等价的
priority_queue<int> q;
priority_queue<int,vector<int>,less<int> >;//后面有一个空格
- 1
- 2
- 3
- 4
- 5
其中第二个参数( vector ),是来承载底层数据结构堆的容器,第三个参数( less ),则是一个比较类,less 表示数字大的优先级高,而 greater 表示数字小的优先级高。
如果想让优先队列总是把最小的元素放在队首,只需进行如下的定义:
priority_queue<int,vector<int>,greater<int> >q;
- 1
- 2
- 3
示例代码:
void test1(){
//默认情况下,数值大的在队首位置(降序)
priority_queue<int> q;
for(int i = 0;i <= 10;i ++)
q.push(i);
while(!q.empty()){
cout<<q.top()<<" ";
q.pop();
}
cout<<endl;
//greater<int>表示数值小的优先级越大
priority_queue<int,vector<int>,greater<int> > Q;
for(int i = 0;i <= 10;i ++)
Q.push(i);
while(!Q.empty()){
cout<<Q.top()<<" ";
Q.pop();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
二、结构体的优先级设置
1.方式一:重载运算符 ‘<’
可以在结构体内部重载 ‘<’,改变小于号的功能(例如把他重载为大于号)
struct student{
int grade;
string name;
//重载运算符,grade 值高的优先级大
friend operator < (student s1,student s2){
return s1.grade < s2.grade;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
示例代码:
void test2(){
priority_queue<student> q;
student s1,s2,s3;
s1.grade = 90;
s1.name = "Tom";
s2.grade = 80;
s2.name = "Jerry";
s3.grade = 100;
s3.name = "Kevin";
q.push(s1);
q.push(s2);
q.push(s3);
while(!q.empty()){
cout<<q.top().name<<":"<<q.top().grade<<endl;
q.pop();
}
}
/* 结果: Kevin:100 Tom:90 Jerry:80 */
- 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
2.方式二:把重载的函数写在结构体外面
将比较函数写在结构体外面,作为参数传给优先队列。
struct fruit{
string name;
int price;
};
struct cmp{
// "<" 表示 price 大的优先级高
bool operator() (fruit f1,fruit f2){
return f1.price < f2.price;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
示例代码:
void test3(){
priority_queue<fruit,vector<fruit>,cmp> q;
fruit f1,f2,f3;
f1.name = "apple";
f1.price = 5;
f2.name = "banana";
f2.price = 6;
f3.name = "pear";
f3.price = 7;
q.push(f1);
q.push(f2);
q.push(f3);
while(!q.empty()){
cout<<q.top().name<<":"<<q.top().price<<endl;
q.pop();
}
}
/* 结果: pear:7 banana:6 apple:5 */
- 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
今天的文章priority_queue使用详解「建议收藏」分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/57941.html