C++学习笔记（七）～ 优先队列（priority
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
优先队列
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;
}
运行结果
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;
}
运行结果
什么情况可以使用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;
}
运行结果
自定义排序方式、使用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;
}
运行结果
