题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

方法

方法：使用最大堆方法
时间复杂度：O((n + k)logk + klogk) = O((n + 2k)logk)

思路

可以使用排序的方法，但效率比较低，且如果碰到数据量大无法一次性读取的时候，就可以采用最大堆的办法。通过建立一个大小为k的最大堆，遍历数组，每个元素与堆顶比较，堆顶为最大堆的最大值，如果小于堆顶，则是更小的数，那么就替换掉最大堆的堆顶，重新调整大小为k的最大堆。遍历完数组后，这个大小为k的最大堆里的k个数字，就是数组中最小的k个数

具体方法

取数组前k个数作为初始化，初始化最大堆。
PS：数组长度小于k则返回空数组
之后从数组第k + 1个数开始遍历，每个数与堆顶相比，如果小于堆顶，则用当前数替换堆顶，然后从堆顶开始调整最大堆，将替换后的数字放到合适的位置，重新暴露出这k个数的最大值到堆顶
遍历结束后，最大堆中的k个数字则是数组中最小的k个数。但是这k个数暂时无序，可以使用排序算法升序排序后输出

代码

function GetLeastNumbers_Solution(input, k) {
  // write code here
  if (input.length < k) {
    return []
  }
  // 使用前k个数建立最大堆
  let bigHeap = input.slice(0, k)
  initHeap(bigHeap)

  // 遍历后面的树，如果比最大堆的堆顶小，则插入
  for (let i = k; i < input.length; i++) {
    let item = input[i]
    if (item < bigHeap[0]) {
      bigHeap[0] = item
      adjustDown(bigHeap, 0)
    }
  }
  return bigHeap.sort()
}

function initHeap (arr) {
  for (let i = arr.length / 2; i >= 0; i--) {
    adjustDown(arr, i)
  }
}

function adjustDown (arr, i) {
  while (2 * i + 1 < arr.length) {
    let child = 2 * i + 1
    if (child !== arr.length - 1 && arr[child] < arr[child + 1]) {
      child++
    }
    if (arr[i] < arr[child]) {
      swap(arr, i, child)
    }
    i = child
  }
}

function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}