题解 | #最小的K个数#

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * 
        * @param input int整型一维数组 
        * @param k int整型 
        * @return int整型一维数组
    */
    fun GetLeastNumbers_Solution(input: IntArray,k: Int): IntArray  {
        if(input.size == 0) return intArrayOf()
        //构建最小堆
        for(i in input.size shr 1 downTo 0) {
            preDown(input, i, input.size)
        }
        val result = IntArray(k)
        //执行k次最小值出堆
        for(i in 1..k) {
            result[i - 1] = input[0]
            input[0] = input[input.size - i]
            preDown(input, 0, input.size - i)
        }
        return result
    }
    
    private fun preDown(array: IntArray, pos: Int, size: Int) {
        var child = (pos shl 1) + 1
        val temp = array[pos]
        var prev = pos
        while(child < size) {
            //先比较两个孩子哪个更小
            if(child + 1 < size && array[child] > array[child + 1]) child++
            //交换值
            if(temp >= array[child]) array[prev] = array[child]
            else break
            prev = child
            //下一层的孩子
            child = (child shl 1) + 1
        }
        //更新原来的值到最后面的index
        array[prev] = temp
    }
}