題目地址：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代碼 手動建堆

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í)堆