題目地址：https://www.acwing.com/problem/content/description/49/
AC代碼 make_heap
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
auto cmp = [](int a,int b){ return a>b; }; //類或者匿名函數(shù)
make_heap(input.begin(),input.end(),cmp);
vector<int> res;
while(k--){
res.push_back(input.front());
pop_heap(input.begin(),input.end(),cmp);
input.pop_back();
}
return res;
}
};
AC代碼 priority_queue
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int,vector<int>,greater<int>> q;
vector<int> res;
for(auto e:input) q.push(e);
while(k--){
res.push_back(q.top());
q.pop();
}
return res;
}
};
AC代碼 手動(dòng)建堆
class Solution {
public:
void adjust_heap(vector<int>& v,int len,int i){
int lc=2*i+1,rc=2*i+2,tar=i;
while(lc<len || rc<len){
if(lc<len && v[lc]<v[tar]) tar=lc;
if(rc<len && v[rc]<v[tar]) tar=rc;
if(tar!=i){
swap(v[i],v[tar]);
i=tar;
lc=2*i+1;
rc=2*i+2;
}
else break;
}
}
void make_heap(vector<int>& v){
for(int i=v.size()/2-1;i>=0;i--)
adjust_heap(v,v.size(),i);
}
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
make_heap(input);
vector<int> res;
while(k--){
res.push_back(input[0]);
swap(input[0],input.back());
input.pop_back();
make_heap(input);
}
return res;
}
};
總結(jié)
復(fù)習(xí)堆
