堆排序算法总结

堆排序的用途很广泛，在面试中也是一个经常会被通过各种角度考到的点：

从1亿个数据里面挑选最大的k个数？
求无序数组的中位数，求第k大数？
等等。。。

堆排序的实现

分为两步：

构建堆
排序

1.首先是构建堆

1.1通过JDK工具类构建堆

构建堆可以自己实现，也可以通过JDk中相应的实现PriorityQueue，PriorityQueue默认是最小堆，如果想要实现最大堆的话，我们可以在初始化时添加一个Comparator比较器，如：

PriorityQueue pq = new PriorityQueue(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

何时选择最大堆？何时选择最小堆？
一般来说，当要对数组进行升序排序时，选择最大堆；反之，选择最小堆。

1.2 自己实现构建堆

代码一：

//摘抄自菜鸟教程：https://www.runoob.com/w3cnote/heap-sort.html
private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

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

代码二：

static void buildSmallHeap(int[] a){
        for (int i = a.length/2; i >=0 ; i--) {
            sink(a,i,a.length);
        }
    }
    //参考priorityQueue中的方法shiftDown方法
    static void sink(int[] a,int k,int len){
        int key = a[k];
        int half = len>>>1;
        while (k<half){
            int child = (k<<1) + 1;//左孩子
            int c = a[child];
            int right = child + 1;//右孩子
            if(right < len && c > a[right])c = a[child = right];//右孩子小于左孩子,对child、c重新赋值
            if(key < a[child]) break;//父节点均小于左右孩子，直接结束
            a[k] = c;
            k = child;
        }
        a[k] = key;
    }

现在我们来分析一下构建堆的时间复杂度：
https://www.cnblogs.com/wongyi/p/7685061.html
https://www.zhihu.com/question/20729324