admin管理员组文章数量:1623801
一、简介
1、优先队列中,元素被赋予优先级,具有最高级先出 (first in, largest out)的行为特征。
2、头文件:#include<queue>
3、定义:
priority_queue<Type, Container, Functional>
其中,Type 为数据类型,Container 为容器类型(Container必须是用数组实现的容器,比如vector,deque等,不能用 list。STL里面默认用的是vector),Functional为比较的方式。
当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆。例如:
升序队列,小顶堆,先弹小的元素出来:priority_queue <int,vector<int>,greater<int> > q;
降序队列,大顶堆,先弹大的元素出来:priority_queue <int,vector<int>, less <int> > q;
greater 和 less 是 std 实现的两个仿函数(就是使一个类的使用看上去像一个函数,其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了。)
二、用法
和队列基本操作相同:
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列
- pop 弹出队头元素
- swap 交换内容
三、例题
题目:给定一个整数数组 nums
和一个整数 k
,请返回其中出现频率前 k
高的元素。可以按 任意顺序 返回答案。
代码:
class Solution {
public:
/*优先队列-小顶堆*/
static bool cmp(pair<int,int> &m,pair<int,int> &n)
{
return m.second>n.second;
}
//或者
//struct cmp{
// bool operator()(pair<int,int> &m,pair<int,int> &n)
// {
// return m.second>n.second;
// }
//};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
for(int x:nums)
mp[x]++;
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> q(cmp);//C++11新标准引入了decltype类型说明符,它的作用是选择并返回操作数的数据类型,在此过程中,编译器分析表达式并得到它的类型,却不实际计算表达式的值。
//或者
//priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
for(auto x:mp)
{
if(q.size()==k)
{
pair<int,int> temp=q.top();
if(x.second>temp.second)
{
q.pop();
q.push(x);
}
}
else q.push(x);
}
vector<int> res;
while(!q.empty())
{
res.push_back(q.top().first);
q.pop();
}
return res;
}
};
本文标签: 例题队列简介priorityqueue
版权声明:本文标题:【C++优先队列】priority_queue简介、用法及例题 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728896458a1178473.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论