题解 | #最小的K个数#

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int > res;
        vector<int> heap = make_heap(input);
        while(k--){
            res.push_back(heap[0]);
            swap(heap[0], heap[heap.size()-1]);
            heap.pop_back();
            down(heap);
        }
        return res;
    }
    vector<int> make_heap(vector<int> input){
        vector<int > heap;
        for(int i = 0; i < input.size(); i++) {
            heap.push_back(input[i]);
            up(heap);
        }
        return heap;
    }
    void up(vector<int>& heap){
        int length = heap.size();
        int i = length - 1;
        while(i){
            int prei = i;
            if(i % 2 == 0){
                if(heap[i] < heap[i/2 - 1]){
                    swap(heap[i], heap[i/2-1]);
                    i = i / 2 - 1;
                }
            }else{
                if(heap[i] < heap[(i-1)/2]){
                    swap(heap[i], heap[(i-1)/2]);
                    i = (i-1) / 2;
                }
            }
            if(prei == i) break;
        }
    }
    void down(vector<int>& heap){
        int length = heap.size();
        int i = 0;
        while(i < length / 2){
            int prei = i;
            int j = 2 * i + 1;
            int k = 2 * (i + 1);
            if(k < length){
                if(heap[j] > heap[k]){
                    j = k; // 保证j最小
                }
            }

            if(heap[i] > heap[j]){
                swap(heap[i], heap[j]);
                i = j;
            }
            if(prei == i) break;
        }
    }
};