题解 | #最小的K个数#

class Solution {
public:

    void heap_min(vector<int>& tree, int i){
        if (tree.size() <= 1) {
            return;
        }

        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (tree[left] < tree[i]) {
            std::swap(tree[left], tree[i]);
        }

        if (right > tree.size() - 1)
            return;

        if (tree[right] < tree[i]) {
            std::swap(tree[right], tree[i]);
        }
    }


    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;

        if(k > input.size()) 
            return result;

        for (int number = 0; number < k; number++) {
            int length = input.size();
            // 进行一次堆化，使第一个元素最小
            for (int i = (length - 2) / 2; i >= 0; i--){
                heap_min(input, i);
            }
            // 交换第一个和最后一个
            std::swap(input[0], input[length - 1]);
            // 添加到结果
            result.push_back(input.back());
            // 删除最后一个元素
            input.pop_back();
        }

        return result;
    }
};