题解 | #最小的K个数# C++ 解法，建堆只排 topk

题解 | #最小的K个数#
C++ 解法，建堆只排 topk

class Solution {
public:
    vector<int> ans;
    void heapify(vector<int> &input, int n, int i) {
        if (i >= n) return ;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int min = i;
        if (l < n && input[l] < input[min]) {
            min = l;
        }
        if (r < n && input[r] < input[min]) {
            min = r;
        }
        if (min != i) {
            swap(input[i], input[min]);
            heapify(input, n, min);
        }
        return ;
    }
    void build_heap(vector<int> &input, int n) {
        int last_node_ind = input.size() - 1;
        int parent = (last_node_ind - 1) >> 1;
        for (int i = parent; i >= 0; --i) {
            heapify(input, n, i);
        }
        return ;
    }
    void my_topk(vector<int> &input, int n, int k) {
        build_heap(input, n);
        for (int i = n - 1; i >= 0 && k; --i) {
            swap(input[i], input[0]);
            ans.push_back(input[i]);
            --k;
            heapify(input, i, 0);
        }
        return ;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k >= input.size()) return input;
        my_topk(input, input.size(), k);
        return ans;
    }
};