题解 | #最小的K个数#

构建一个堆。进行堆排序

参考：

文章：https://kouder.cn/post/zui-xiao-de-k-ge-shu/
视频：https://www.bilibili.com/video/BV1Eb41147dK

function GetLeastNumbers_Solution(input, k) {
    // write code here
    if (k > input.length) {
        return [];
    }
    function swap(arr, i, j) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 从一个节点,开始自上至下
    function heapify(arr, n, i) {
        // n: 使用的arr长度,从0开始
        // i: 当前节点的索引位置
        // arr: 一维数组表示的堆

        // 递归的结束条件
        if (i >= n) {
            return;
        }

        let min = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        // 比较其左右节点与自身的三个值,得到最大值
        if (left <= n && arr[left] < arr[min]) {
            min = left;
        }
        if (right <= n && arr[right] < arr[min]) {
            min = right;
        }
        if (min !== i) {
            swap(arr, i, min);
            heapify(arr, n, min);
        } else {
            return  // min就是i时不用解了,退出
        }
    }

    function buildHeap(arr) {
        // 需要借助heapify方法
        let last = arr.length - 1;
        last = Math.floor((last - 1) / 2);
        while (last >= 0) {
            heapify(arr, arr.length - 1, last);
            last -= 1;
        }
    }

    // 前 k 个
    function sortByHeap(arr, k) {
        buildHeap(arr);
        let n = arr.length - 1;
        const sortedArr = [];
        const stop = n - k;
        while (n > stop) {
            sortedArr.push(arr[0]);
            swap(arr, 0, n);
            // 不用截断数组, 直接把arr长度"改掉"
            heapify(arr, n - 1, 0);
            n -= 1;
        }
        return sortedArr;
    }
    // console.log(sortByHeap(input, k));
    return sortByHeap(input, k);
}

// const arr = [7, 9, 11, 15, 17, 6, 13];
// GetLeastNumbers_Solution(arr, 3)