public static ArrayList<Integer> GetLeastNumbers_Solution1(int[] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if (input==null||input.length==0||input.length<k||k<=0) {
            return arrayList;
        }

        for (int i = 0; i < k; i++) {
            arrayList.add(input[i]);
            insert(arrayList, i);
        }
        for (int i = k; i < input.length; i++) {
            if (input[i]<arrayList.get(0)) {
                arrayList.set(0, input[i]);
                heapify(arrayList);
            }
        }
        
        return arrayList;
    }
    public static void swap(ArrayList<Integer>arr,int i,int j) {
        int temp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, temp);
        
    }
    public static void  insert(ArrayList<Integer>arr,int i) {
        while (i!=0) {
            int parent = (i-1)/2;
            if (arr.get(parent)<arr.get(i)) {
                swap(arr, parent, i);
                i = parent;
            } else {
                break;
            }
        }
    }
    public static void heapify(ArrayList<Integer> arr) {
        int index = 0;
        int largest = 0;
        int left = 2*index+1;
        int right = 2*index+2;
        while (left<arr.size()) {
            if (arr.get(left)>arr.get(index)) {
                largest = left;
            }
            if (right<arr.size()&&arr.get(largest)<arr.get(right)) {
                largest = right;
            }
            if (largest!=index) {
                swap(arr, index, largest);
            } else {
                break;
            }
            
            index = largest;
            left = 2*index+1;
            right = 2*index+2;
        }
    }