admin管理员组文章数量:1623796
c++ priority_queue是优先队列,可以用来实现大根堆和小根堆。
默认priority_queue是大根堆。
priority_queue<int> pq; // 大根堆
//等同于priority_queue<int, vector<int>, std::less<int>> pq;
priority_queue的模板类型是:
template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> class priority_queue
可以看出priority_queue 实例默认有一个 vector 容器。函数对象类型 less 是一个默认的排序断言,决定了容器中最大的元素会排在队列前面。greater,决定了容器中最小的元素会排在队列前面。当然,如果指定模板的最后一个参数,就必须提供另外的两个模板类型参数。
常用操作
push() : 向队列中传入数据,传进去之后priority_queue会自动进行排序,不用你操心
pop() : 是将数组第一个元素弹出,也就是堆顶元素。对于大根堆来说是最大的值,对于小根堆来说是最小的值。
top() : 返回堆顶的元素。
以上三个是最常用的,还有几个其他的:
size() : 返回元素个数
emplace() : 作用同push()
empty() : 判断是否为空。
如何重写priority_queue的排序断言
下面给个例子,自己写一个满足要求的mycomparison
题目参考leetcode: 347. 前 K 个高频元素
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
if(nums.size() == 0) return res;
unordered_map<int, int> m;
for(int i = 0; i < nums.size(); i++)
{
m[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> q;
for(unordered_map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
q.push(*it);
if(q.size() > k)
{
q.pop();
}
}
while(!q.empty())
{
auto temp = q.top();
res.push_back(temp.first);
q.pop();
}
return res;
}
本文标签: priorityqueue
版权声明:本文标题:c++ priority_queue用法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728896336a1178458.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论