题解 | #最小的K个数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param input int整型一维数组 
 * @param k int整型 
 * @return int整型一维数组
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
/**
 * 解题思路: 大顶堆(leetcode)
 * **************************************************************************
 */
var GetLeastNumbers_Solution = function(nums, k) {
    // 边界情况
    if (nums.length <= 0) return []
    if (k <= 0) return []
    if (nums.length <= k) return nums
    const maxK = nums.length - k
    // 非边界情况
    heapSrot(nums, maxK)
    return nums.slice(0, k)
};

function heapSrot(nums, k) {
    buildHeap(nums)
    let count = 0
    for (let i = nums.length - 1; i >= 0; i--) {
        swap(nums, 0, i)
        count += 1
        if (k === count) {
            return nums[nums.length - k]
        }
        heapify(nums, i, 0)
    }
}
function buildHeap(nums) {
    const lastChild = nums.length - 1
    const lastChildParent = Number.parseInt((lastChild - 1) / 2)
    for (let i = lastChildParent; i >= 0; i--) {
        heapify(nums, nums.length, i)
    }
}
/**
 */
function heapify(nums, n, i) {
    if  (i >= n) return // 加的
    const childLeft = 2 * i + 1
    const childRight = 2 * i + 2
    let maxIndex = i
    if (childLeft < n && nums[childLeft] > nums[maxIndex]) {
        maxIndex = childLeft
    }
    if (childRight < n && nums[childRight] > nums[maxIndex]) {
        maxIndex = childRight
    }
    if (i !== maxIndex) {
        swap(nums, i, maxIndex)
        heapify(nums, n, maxIndex) // !!!这块要注意
    }
}

function swap(nums, i , j) {
    const temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

module.exports = {
    GetLeastNumbers_Solution : GetLeastNumbers_Solution
};