admin管理员组文章数量:1624352
- 优先级队列：一种容器适配器，按照严格的弱排序标准，它的第一个元素是它所包含的最大的元素。
- 优先级队列默认使用Vector作为其底层存储数据的容器，在Vector上又使用了堆的算法，将Vector中的元素构造成堆的结构，所以，priority_queue就是堆 ，默认其为大堆（其底层按照小于号来比较）。
- 如果是要建立小堆，则应该利用greater比较方式，所需头文件为< functional >。
#include <functional>
void TestPriority_queue(){
vector<int> v1{3,4,1,0,2,7};
priority_queue <int> q1;
for (auto& e : v){
q1.push(e);
}
cout << q1.top() << endl;
**priority_queue <int, vector<int>, greater<int>> q2(v.begin(),v.end());**
cout << q2.top() << endl;
}
结果如图所示：
-
如果要在priority_queue中放自定义类型的数据，则需要在自定义类型中提供 > 或 < 的重载。
-
数组中的第k个最大元素：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
1.利用priority_queue.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k){
priority_queue<int> pq;
for (auto e: nums){
pq.push(e);
}
while(--k){
pq.pop();
}
return pq.top();
}
2.利用数组排序.（默认为大堆）
class Solution {
public:
int findKthLargest(vector<int>& nums, int k){
sort(nums.begin(),nums.end());
return nums[nums.size()-k];
}
3.利用数组排序. （修改为小堆）
class Solution {
public:
int findKthLargest(vector<int>& nums, int k){
sort(nums.begin(),nums..end(),greater<int>());
return nums[k-1];
}
本文标签： 组中元素priorityqueue
版权声明：本文标题：Priority_queue及应用（数组中的第k个最大元素）。 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728897931a1178654.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论