题解 | #最小的K个数#

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
        if (k == 0) {
            return new ArrayList<>();
        }
        int length = input.length;
        for (int i = length / 2 - 1; i >= 0; --i) {
            adjustHeap(input, i, length);
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = length - 1; i >= 0; --i) {

            int minValue = input[0];
            input[0] = input[i];
            input[i] = minValue;

            result.add(minValue);
            if (result.size() >= k) {
                break;
            }
            adjustHeap(input, 0, i);
        }
        return result;
    }

    private void adjustHeap(int[] array, int parent, int length) {

        int temp = array[parent];
        int child = 2 * parent + 1;

        while (child < length) {

            if (child + 1 < length && array[child] > array[child + 1]) {
                ++child;
            }

            if (temp <= array[child]) {
                break;
            }

            array[parent] = array[child];
            parent = child;
            child = 2 * child + 1;
        }

        array[parent] = temp;
    }