题解 | #最小的K个数#利用大根堆，注意k==1的情况

 import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //思路一、对数组进行排序 取前k个值
        ArrayList<Integer> result = new ArrayList<>();
        if(input == null || input.length == 0 || k == 0){
            return result;
        }
        if(k >= input.length){
            for(int i = 0;i<input.length;i++){
                result.add(input[i]);
            }
        } else {
            if(k == 1){
                //直接寻找
                int min = input[0];
                for(int i = 1;i<input.length;i++){
                    if(input[i] < min){
                        min = input[i];
                    }
                }
                result.add(min);
            } else {
                //Arrays.sort(input);     
                //思路二、利用大根堆
                heapSort(input,k);
                for(int i = 0;i<k;i++){
                    result.add(input[i]);
                }
            }

        }
        return result;
    }
    
    private void heapSort(int[] input, int k){
        //第一步 对前K个数进行原地建堆 采用自下而上的下滤方式建堆
        //从第一个非叶子节点开始
        int beginIndex = (k >> 1) - 1;
        for(int i = beginIndex;i>=0;i--){
            siftDown(i,input,k);
        }
        //第二步 遍历后续元素 只要是小于堆顶就交互 然后下坠
        for(int i = k;i<input.length;i++){
            if(input[i] < input[0]){
                swap(input,i,0);
                //交互完了 对堆顶执行下滤操作
                siftDown(0,input,k);
            }
        }
    }
    
    private void siftDown(int i,int[] input, int k){
        //当前点的值
        int cur = input[i];
        //如果小于左节点或者右节点就交互
        int leftIndex = i * 2 + 1;
        int rightIndex = leftIndex + 1;
        int maxIndex = leftIndex;
        //右节点不一定存在
        if(rightIndex < k){
            //右节点存在
            if(input[leftIndex] < input[rightIndex]){
                maxIndex = rightIndex;
            }
        }
        if(cur < input[maxIndex]){
            swap(input,i,maxIndex);
            //交互完以后要继续判断是否还得下滤
            int limitIndex = (k >> 1) - 1;
            if(maxIndex <= limitIndex){
                siftDown(maxIndex,input,k);
            }
        }
    }
    
    private void swap(int[] input,int index1,int index2){
        int temp = input[index1];
        input[index1] = input[index2];
        input[index2] = temp;
    }
}