题解 | #最小的K个数#

里补充一下大根堆和小根堆的知识点，大根堆就是对于每个结点，其根结点最大；小根堆就是最小的放到根节点里面，每插入一个数字，然后就可以根据堆的情况进行调整。这里可以手动实现，也可以用STL里面的优先队列。这样就省去了我们对堆的调整，每次操作直接取堆顶就行了。这里注意的是如果自己实现堆的话可能堆的情况不止一种，但是不会影响最后的结果。，可以结合下面这个图进行理解。

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
//         ArrayList<Integer> list = new ArrayList();
//         quickSort(input,0,input.length-1);

//         if(k<=input.length){
//             for(int i=0;i<k;i++){
//                 list.add(input[i]);
//             }
//         }
//         return list;

        return bigHeap(input, k);
    }

    public void quickSort(int [] arr,int low,int high){
        int i,j,temp;

        if(low>high){
            return;
        }

        i = low;
        j = high;
        temp = arr[low];

        while(i<j){

            while(i<j && temp <= arr[j]){
                j--;
            }

            while(i<j && temp >= arr[i]){
                i++;
            }

            if(i<j){
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }

        arr[low] = arr[i];
        arr[i] = temp;

        quickSort(arr,low,i-1);
        quickSort(arr,i+1,high);
    }

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

        ArrayList<Integer> result = new ArrayList<>(k);

        //根据题意要求，如果K>数组的长度，返回一个空的数组
        if (k > input.length || k == 0) {
            return result;
        }

        /**
         * 创建最大堆 看PriorityQueue的offer源码可知:
         * public boolean offer(E e) {
         *         if (e == null)
         *             throw new NullPointerException();
         *         modCount++;
         *         int i = size;
         *         if (i >= queue.length)
         *             grow(i + 1);
         *         size = i + 1;
         *         if (i == 0)
         *             queue[0] = e;
         *         else
         *             siftUp(i, e);
         *         return true;
         *     }
         * siftUp(i, e)这个方法，当插入的元素不是顶部位置，会进行内容排序调整，siftUp(i, e)方法就是起到这个作用
         * 默认的插入规则中，新加入的元素可能会破坏小顶堆或大顶堆的性质，因此需要进行调整。
         * 调整的过程为：从尾部下标的位置开始，将加入的元素逐层与当前点的父节点的内容进行比较并交换，直到满足父节点内容都小于或大于子节点的内容为止。
         * private void siftUp(int k, E x) {
         *     while (k > 0) {
         *         int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
         *         Object e = queue[parent];
         *         if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
         *             break;
         *         queue[k] = e;
         *         k = parent;
         *     }
         *     queue[k] = x;
         * }
         *
         * 这里覆盖的比较器,num1是要被添加的元素,num2是堆顶元素,第一次放入第一个元素,直接队列头元素赋值为该第一个元素,后续
         * 放入第N个元素的时候,会执行siftUp 紧随着会执行比较器 根据比较器构建最大堆还是最小堆
         * siftUp(i, e)这个方法:默认的插入规则中，新加入的元素可能会破坏小顶堆或大顶堆的性质，因此需要进行调整。
         * 调整的过程为：从尾部下标的位置开始，将加入的元素逐层与当前点的父节点的内容进行比较并交换，直到满足父节点内容都小于或大于子节点的内容为止。
         * 
         * 我们重写的比较器是:comparator：表示比较器对象，如果为空，使用自然排序
         * (num1, num2) -> num2 - num1
         * 所以代表 堆内父子节点元素按照大到小排序 构成大顶堆
         */
        PriorityQueue<Integer> bigHeap = new PriorityQueue<>(new Comparator<Integer>() {
            //结合自定义比较器 构建大顶堆, 如果不重写比较器,那么默认为小顶堆
            @Override
            public int compare (Integer num1, Integer num2) {
                return num2 - num1;
            }
        });

        for (int i = 0; i < k; i++) {
            bigHeap.offer(input[i]);
        }

        //因为是最大堆，也就是堆顶的元素是堆中最大的，遍历数组后面元素的时候，
        //如果当前元素比堆顶元素小，就把堆顶元素给移除，然后再把当前元素放到堆中
        for (int j = k; j < input.length; j++) {

            if (bigHeap.peek() > input[j]) {
                bigHeap.poll();
                bigHeap.offer(input[j]);
            }
        }

        for (int h = k - 1; h >= 0; h--) {
            result.add(bigHeap.poll());
        }

        return result;
    }
}