当前位置 博文首页 > 中流击水,浪遏飞舟:堆方法&&剑指 Offer 40. 最小的k个
c++优先队列(priority_queue)用法详解
//升序队列,小根堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列,大根堆
priority_queue <int,vector<int>,less<int> >q;
与sort()函数中的less< data-type >默认升序,grater< data-type >降序方法不同,注意区分。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if(!k){
return {};
}
priority_queue<int> q; //优先队列,c++中默认大根堆
vector<int>num;
int i=0;
while(i<k){
q.push(arr[i]);
i++;
}
while(i<arr.size()){
if(arr[i]<q.top()){
q.pop();
q.push(arr[i]);
}
i++;
}
while(!q.empty()){
num.push_back(q.top());
q.pop();
}
return num;
}
};
cs