小根堆或优先队列

使用小根堆进行堆排序
解法一：
创建一个小根堆

class Heap{

    private List<Integer>  heap = new ArrayList<Integer>();


    public Heap(int[] Object){

        for (int e : Object) {
            add(e);
        }
    }


    public void add(int element){

        heap.add(element);
        int curIndex = heap.size() - 1;

        while (curIndex > 0){

            int parentIndex = (curIndex - 1) / 2;

            if (heap.get(curIndex) < heap.get(parentIndex)){

                int temp = heap.get(parentIndex);
                heap.set(parentIndex,heap.get(curIndex));
                heap.set(curIndex,temp);
                curIndex = parentIndex;
            }else {
                break;
            }

        }
    }

    public int remove(){

        int removeObject = heap.get(0);
        heap.set(0,heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int curIndex = 0;

        while (curIndex < heap.size()){

            int leftChildIndex = 2 * curIndex + 1;
            int rightChildIndex = 2 * curIndex + 2;

            int minChildIndex = leftChildIndex;

            if (leftChildIndex >= heap.size() || rightChildIndex >= heap.size()){
                break;
            }

            if (heap.get(leftChildIndex) > heap.get(rightChildIndex)){

                minChildIndex = rightChildIndex;
            }

            if (heap.get(curIndex) > heap.get(minChildIndex)){

                int temp = heap.get(curIndex);
                heap.set(curIndex,heap.get(minChildIndex));
                heap.set(minChildIndex,temp);
                curIndex = minChildIndex;
            }else {
                break;
            }

        }

        return removeObject;
    }
}

进行堆排序

    public ArrayList<Integer> GetLeastNumbers_Solution2(int[] input, int k) {

        if (input == null || input.length < k || input.length == 0){
            return new ArrayList<Integer>();
        }

        Heap heap = new Heap(input);

        ArrayList<Integer> res = new ArrayList<>();

        for (int i = 0; i < k; i++) {

            res.add(heap.remove());
        }

        return res;
    }

解法二：
使用Java自带的优先队列，这个优先队列本身就是一个小根堆

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {

        if (input == null || input.length < k){
            new ArrayList<Integer>();
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for (int i : input) {
            heap.add(i);
        }

        ArrayList<Integer> res = new ArrayList<>();

        for (int i = 0; i < k; i++) {

            res.add(heap.remove());
        }

        return res;
    }