public class GetMinKNums {
    //向堆中插入元素
    public static void insert(int[] arr, int index, int value) {
        arr[index] = value;
        while (index != 0) {
            int parent = (index - 1) / 2;
            if (arr[parent] < arr[index]) {
                swap(arr, parent, index);
                index = parent;
            } else {
                break;
            }
        }
    }

    //arr[0]向下进行heapify过程
    public static void heapify(int[] arr) {
        int index = 0;
        int left = 2 * index + 1;
        int right = left + 1;
        int largest = index;
        while (left < arr.length) {
            if (arr[left] > arr[index]) {
                largest = left;
            }
            if (right < arr.length && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest != index) {
                swap(arr, largest, index);
            } else {
                break;
            }
            index = largest;
            left = 2 * index + 1;
            right = left + 1;
        }
    }

    public static int[] getMinKNumsByHeap(int[] arr, int k) {
        if (k < 1 || k > arr.length) {
            return arr;
        }

        int[] kHeap = new int[k];
        for (int i = 0; i < k; i++) {
            insert(kHeap, i, arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < kHeap[0]) {
                kHeap[0] = arr[i];
                heapify(kHeap);
            }
        }
        return kHeap;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        int[] res = getMinKNumsByHeap(arr, 5);
        for (int i : res) {
            System.out.print(i + " ");
        }

    }
}