题解 | #最小的K个数# 对前K个数建立大顶堆

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input == null || input.length == 0 || k == 0) {
            return res;
        }
        if (k == 1) {
            //直接查找
            int target = input[0];
            for (int i = 1; i < input.length; i++) {
                if (input[i] < target) {
                    target = input[i];
                }
            }
            res.add(target);
            return res;
        }

        //特殊情况处理完毕 开始处理正常情况
        //第一步 对前k个数进行原地建堆 采用大顶堆
        int index = (k >> 1) - 1;
        for (int i = index; i >= 0; i--) {
            siftDown(input, i, k);
        }
        //第二步 不断从剩余的数中比大顶堆顶部小的数 替换进堆中
        for (int i = k; i < input.length; i++) {
            if (input[i] < input[0]) {
                swap(input, 0, i);
                siftDown(input, 0, k);
            }
        }

        //第3步 对前K个数进行快速排序
        quickSort(input, 0, k - 1);
        //第4步 将前K个数 就是堆中的数据 放入集合返回
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

    private void siftDown(int[] arr, int index, int length) {
        int limitIndex = (length >> 1) - 1;
        if (index > limitIndex) {
            return;
        }
        int left = index * 2 + 1;
        int right = left + 1;
        int maxIndex = left;
        if (right < length) {
            maxIndex = arr[left] >= arr[right] ? left : right;
        }
        if (arr[maxIndex] > arr[index]) {
            swap(arr, maxIndex, index);
            siftDown(arr, maxIndex, length);
        }
    }

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

    private void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int left = begin;
        int right = end;
        int cur = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= cur) {
                right --;
            }
            if (left < right) {
                swap(arr, left, right);
            }
            while (left < right && arr[left] <= cur) {
                left ++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        quickSort(arr, begin, left - 1);
        quickSort(arr, left + 1, end);
    }
}