题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution { public ArrayList GetLeastNumbers_Solution(int [] input, int k) { ArrayList list = new ArrayList<>();

    if(k ==0){
        return list;
    }
    
    for(int i=0;i<k;i++){
        list.add(input[i]);
        heapInsert(list, i);
    }
    
    for(int i = k;i<input.length;i++){
        if(input[i]<list.get(0)){
            list.remove(0);
            list.add(0,input[i]);
            heapify(list, 0);
        }
    }
    
    return list;
    
}

public static void heapify(ArrayList<Integer> list, int i){
    while(i < list.size()){
        int left = 2*i+1 <list.size()?2*i+1:i;
        int right = 2*i+2 <list.size()?2*i+2:i;
        int max = list.get(left) < list.get(right)? right:left;

        if(i != max && list.get(i)< list.get(max)){
            swap(list, i, max);
            i = max;
        }else{
            break;
        }
    }
    
}

public static void heapInsert(ArrayList<Integer> list, int i){
    while(list.get(i) > list.get((i-1)/2)){
        swap(list, i, (i-1)/2);
        i= (i-1)/2;
    }
}

public static void swap(ArrayList<Integer> list, int i, int j){
    int a = list.get(i);
    int b = list.get(j);
    list.remove(i);
    list.add(i, b);
    list.remove(j);
    list.add(j, a);
}

}