输入整数数组?arr?，找出其中最小的?k?个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1 输出：[0]
排序
先排序在输出前k个数
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var getLeastNumbers = function(arr, k) {
arr.sort((a,b)=>a-b)
return arr.slice(0,k)
};堆
1.创建小根堆
2.然后按堆排序的思路逐步推出最小值
3.每次推出后重新调整堆，保持小根堆
4.这样推出的前 k 个数就是需要求的值
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var getLeastNumbers = function(arr, k) {
let resultArray = []
const arrLength = arr.length
if(k === 0){
return []
}
if(k === arr.length){
return arr
}
createHeap(arr)
for(let i = 1; i <= k; i++){
resultArray.push(arr[0])
swap(arr, 0, arrLength - i)
ajustTree(arr, 0, arrLength - i)
}
return resultArray
};
var createHeap = function(arr){
const arrLength = arr.length
for(let i = Math.floor(arrLength / 2); i >= 0; i --){
ajustTree(arr, i, arrLength)
}
}
/**
* 调整数组形式的完美二叉树，保证根节点最小
*/
var ajustTree = function(arr, treeRootI, treeLength){
// 用 child 指向左孩子
let child = treeRootI * 2 + 1
// 保证孩子节点存在
while(child < treeLength){
// 比较孩子节点，child 取小的那个
if(child + 1 < treeLength && arr[child] > arr[child + 1]){
child = child + 1
}
// 如果根节点比孩子节点大互换，互换后根节点指向孩子节点，孩子节点指向孙子节点
if(arr[treeRootI] > arr[child]){
swap(arr, treeRootI, child)
treeRootI = child
child = 2 * treeRootI + 1
}
else{
// 避免死循环
break
}
}
}
var swap = function(arr, i, j){
if(i === j){
return
}
arr[i] = arr[i] + arr[j]
arr[j] = arr[i] - arr[j]
arr[i] = arr[i] - arr[j]
}
