C++学习笔记（七）～ 优先队列（priority_queue）的简单使用
优先队列
priority_queue：优先队列，本质是堆实现。与队列不同的是，priority_queue只能访问队列头部的信息（使用top），且插入元素后，会自动排序。
基本操作:
- top(): 访问队头元素
- empty(): 队列是否为空
- size():返回队列内元素个数
- push():插入元素到队尾 (并排序)
- emplace():原地构造一个元素并插入队列
- pop():弹出队头元素
- swap():交换内容
priority_queue<Type, Container, Functional>
-
Type ：数据类型，就是优先队列中每一个元素的数据类型
-
Container ：容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）【简单理解就是用什么容器实现这个优先级队列】
-
Functional ：比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆【有greater、less和自定义函数，其中greater使得优先队列中的元素升序排列，所以第一个元素（头部）就是最小的元素，也就是小顶堆；less使得元素降序排列，那么第一个元素就是最大的，也就是大顶堆。】
Demo — greater()，小顶堆
#include<iostream>
#include<queue> // 使用priority_queue只需要引入 queue 即可
using namespace std;
int main()
{ // 注意这里需要留一个空格 不然编译器会报错，误以为是>> 应该写成> > priority_queue<int,vector<int>,greater<int> > a; a.push(2); a.push(1);
// 此时优先队列内部是： 1--2 int temp=a.top(); // 应该排序规则我们选的是 greater 意思是 升序排列 ， 又因为只可以访问队列头部元素 // 所以每次访问其实就是访问的最小的那个值 是小顶堆【堆顶最小】 cout<<"temp="<<temp<<endl; return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
运行结果
Demo — less()，大顶堆，【第三参数不填，默认是less】
#include<iostream>
#include<queue>
using namespace std;
int main()
{ // 注意这里需要留一个空格 不然编译器会报错，误以为是>> 应该写成> > priority_queue<int,vector<int>,less<int> > a; a.push(2); a.push(1); a.push(4); // 此时优先队列内部是： 4--2--1 // 因为在push操作的时候，自动会按照排序规则进行排序 int temp=a.top(); cout<<"temp="<<temp<<endl; return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
运行结果
什么情况可以使用priority_queue呢？
答：emmmm，可以想象一个场景：给你一个50人的数学成绩，你的任务就是找出前三名的成绩。 【看到这肯定觉得太简单了，先排序，再找前三就OK了，确实可以这样做，不过我们可以使用优先队列（情况复杂时，就可以体现出优先队列的好处了）】
例子：有十个同学对成绩是0、1、2。。。9分，请返回前三名的成绩。
#include<iostream>
#include<queue>
using namespace std;
int main()
{ //初始化数组math为 0 1 2 3 。。。9 vector<int> math; for(int i=0;i<10;++i) math.push_back(i); //假设我们需要返回前三名 按照第一 第二 第三的顺序 // 思路： // 首先可以确定的是我们优先队列中只可以包含三个元素，即前三名的成绩 // 那么是选用greater 还是less呢 // 假设使用less， 那么头部元素就是最大的，而每次对优先队列访问的时候，只可以访问头部 // 那么每次其实都是与队列中最大的值进行比较 而没有对剩余对两个数比较 难以达到要求 // 假设使用greater 那么头部元素最小（三个中最小），每次进行比较时，都是与最小的进行比较 // 如果该元素大于此时的最小值，那么说明此时的头部元素一定不是最终的前三名，【因为本来队列中就有两个比它大，然后又一个元素比他大，那么他肯定不是前三】 // 所以直接pop出此时的头部元素，将该元素【比较时大的这个数】压入优先队列，至于与其他两个数的大小，我们不需要关系，因为反正我们可以确定它在前三 // 如果此时队列的size() 【也是队列中元素的数量】小于3，那么直接将元素压入即可 // 综上：我们选择使用 greater priority_queue<int,vector<int>,greater<int> > a;//定义一个优先队列a， 注意此时的写法 for(int i=0;i<math.size();++i) { if(a.size()==3) { if(math[i]>a.top()) { a.pop(); a.push(math[i]);// 压入的时候，会自动排序 } } else { a.push(math[i]); } } // 使用vector<int> ans接收答案 vector<int> ans; while(!a.empty()) { ans.push_back(a.top()); a.pop(); } // 因为队列此时是升序排列的：7--8--9 而我们需要的是9--8--7 // 那么只需要对ans反序即可 reverse(ans.begin(),ans.end()); // 验证结果 for(int i=0;i<ans.size();++i) { cout<<ans[i]<<endl; } return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
运行结果
自定义排序方式、使用emplace()
swap():交换容器中的内容
测试Demo
#include<iostream>
#include<queue>
using namespace std;
int main()
{ priority_queue<int,vector<int>,greater<int> > a; priority_queue<int,vector<int>,greater<int> > b; a.push(1); a.push(2); a.push(3); b.push(4); b.push(5); a.swap(b);// 使用b.swap(a)效果一样 cout<<"a:"<<endl; while (!a.empty()) { cout<<a.top()<<endl; a.pop(); } cout<<endl; cout<<"b:"<<endl; while(!b.empty()) { cout<<b.top()<<endl; b.pop(); } return 0;
}
- 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
- 31
- 32
运行结果
文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。
原文链接：haihong.blog.csdn.net/article/details/108567330
- 点赞
- 收藏
- 关注作者
评论（0）