优先队列
一、概念
1.定义
优先队列是一种特殊的队列，作为缓存结构，它和队列、栈类似，都可以将元素保存其中，再按照一定的顺序访问和弹出。优先队列的特点在于不按照进队的次序决定出队次序，而是按照我们逻辑设定的优先级来决定出队的次序。
2.分类
二、底层结构
实现优先队列的方式有很多，二叉堆、二项堆、斐波那契堆等等，但这些都是堆的实现方式。事实上，优先队列也可以使用不同的底层结构实现（见下图），可以看到综合性能最优的还是使用堆这种数据结构。
三、二叉堆（binary heap）
1、概念
2、存储结构
3、用二叉堆实现优先队列
（1）抽象数据类
注意：capacity是数组的容量，size是当前数组中有效元素的个数，heap为数组
（2）插入操作
（3）删除操作
四、优先队列的应用
1、应用场景举例
2、编程题举例
数组出现频率问题：
vector<int> topKFrequent(vector<int> nums , int k)
{
unordered_map<int,int> map;
for(int i: nums) map[i]++;//遇见相同的键值对应的value就++，这样通过foreach语句遍历nums数组后就可以将不同元素出现的频次记录在map中
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;//声明一个最小堆
for(auto it:map)
{
if(q.size() == k)
{
if(it.second > q.top().first)
{
q,pop();
q.push(make_pair(it.second,it.first));
}
}
else
q.push(make_pair(it.second,it.first));
}
vector<int> ans;
while(q.size())
{
ans.push_back(q.top().second);
q.pop();
}
return vector<int>(res.rbegin(),res.rend());
//反向迭代器
} 五、c++STL库中的priority_queue
1、基本参数设置
2、小顶堆
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
int x ,y;
Node(int a = 0, int b = 0):x(a),y(b){}
};
struct cmp
{
bool operator()(Node a , Node b)
{
if(a.x == b.x) return a.y > b.y
else return a.x > b.x;
}
}
void test()
{
priority_queue<Node,vector<Node>,cmp> q;
for(int i = 0; i < 10; ++i)
{
q.push(Node(rand(),rand()));
}
while(!q.empty())
{
cout << q.top().x << " " << q.top().y << endl;
q.pop();
}
} 3.基本操作
4、用pair做优先队列元素
5、用自定义类型做优先队列元素
