题解 | #最小的K个数#

我看到很多人都是使用的快速排序，这里分享一个使用最大堆的方式：

运行时间：3ms
占用内存：512KB

class Solution {
public:
    // miniK 使用最大堆
    void max_heapfiy(vector<int>& input, int begin, int end) {
        int    l       = begin * 2 + 1;
        int    r       = begin * 2 + 2;
        size_t largest = begin;
        if(l < end && input[l] > input[largest]) largest = l;
        if(r < end && input[r] > input[largest]) largest = r;
        if(largest != begin) {
            swap(input[begin], input[largest]);
            max_heapfiy(input, largest, end);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        // 构建堆
        for(int i = k / 2; i >= 0; --i) max_heapfiy(input, i, k);
        for(int i = k; i < input.size(); ++i) {
            if(input[i] < input[0]) {
                swap(input[0], input[i]);
                max_heapfiy(input, 0, k);
            }
        }
        return {input.begin(), input.begin() + k};
    }
};

这里唯一需要特别注意的是第十八行一定要是 int i = k 因为如果更小的话会导致堆顶与堆底元素发生交换，这时因为顶点的左右孩子没有变化，因此不会触发维护算法。这时就出错了。

比较遗憾的是看来测试集中没有大数据集，因此最大堆的好处体现不出来。反而比快速排序还要慢：