admin管理员组文章数量:1623796
一、概念
大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
二、C++如何实现大顶堆和小顶堆
通过优先队列priority_queue模拟大（小）顶堆,优先级高的元素先出队列，并非按照先进先出的要求，其基本操作和队列相同。
定义：priority_queue<Type, Container, Functional>
Type 就是数据类型
Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
priority_queue<int> a; // 默认大顶堆//greater和less是std实现的两个仿函数
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;
示例（Top k）：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> ret;
unordered_map<int, int> mp;
priority_queue<pair<int, int>> pq; // 大顶堆，第一个最大
for (auto i : nums)
mp[i]++;
for (auto p : mp) {
pq.push(pair<int, int>(-p.second, p.first));
if (pq.size() > k) pq.pop();
}
while (k--) {
ret.push_back(pq.top().second);
pq.pop();
}
return ret;
}
};
void main() {
Solution s;
vector <int> a{ 1,2,2,2,4,4,4,4,4,4,7,7,8,10 };
auto ssss = s.topKFrequent(a, 3);
for (auto& t : ssss) {
cout << t << " ";
}
}本文标签： priorityqueue大顶堆小顶堆
版权声明：本文标题：priority_queue（大顶堆、小顶堆） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728895693a1178378.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论