题解 | #求二叉树的层序遍历#

构建大根堆，sift函数进行调整，堆的构建是从最后面最小单位构建的，前k个构建完成后，对后面的数和堆顶比较，如果比堆顶小就覆盖堆顶，并进行一次sift函数也就是堆构建

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arr= new ArrayList<Integer>();
        
        if(input.length==0|| k==0){
            return arr;
        }
        int[] heap = new int[k];
        for(int i=0;i<k;i++){
            heap[i]=input[i];
        }
        int low=(k-2)/2;
        
        for(int i=low;i>=0;i--){
            sift(heap,i,k-1);
        }
        for(int i=k;i<input.length;i++){
            if(heap[0]>input[i]){
                heap[0]=input[i];
                sift(heap,0,k-1);
            }
        }
        for(int i=0;i<k;i++){
            arr.add(heap[i]);
        }
        return arr;
    }
    public void sift(int[] arr, int low,int high){
        int i=low;
        int j=low*2+1;
        int temp = arr[low];
        while(j<=high){
            if(j+1<=high && arr[j]< arr[j+1]){
                j= j+1;
            }
            if(arr[j]>temp){
                arr[i]=arr[j];
                i=j;
                j=i*2+1;
            }else{
                arr[i]=temp;
                break;
            }
        }
        arr[i] = temp;
    }
}