堆排序（拓展：堆、优先队列）

7.堆排序（快，不稳，使用较多）

总结

时间复杂度O(N*logN)，额外空间复杂度O(1)
堆结构非常重要
1，堆结构的heapInsert与heapify
2，堆结构的增大和减少
3，如果只是建立堆的过程，时间复杂度为O(N)
4，优先级队列结构，就是堆结构

大根堆的插入heapInsert

将一个数加入到堆中的过程：

1.首先与父亲节点比较，当比父节点大时，发生交互，并更新自己的index；

2.重复步骤1。直到比父节点小，或者已经到堆顶时，停止。

时间复杂度：logN,最多比较已有数的高度。

static void heapInsert(int[] a,int index){
    int parent = (index-1)/2;
    while(a[parent]<a[index]){//边界值分析:当到顶点时,index=0;父节点(0-1)/2=0;同样跳出循环
        swap(a,parent,index);
        index = (index-1)/2;
    }
}

创建一个大根堆：

将一个数组的从0到尾，依次调用heapInsert函数，一个一个插入到堆中。

时间复杂度：N. 原因：log1+log2+log3+...+logN=N

for(int i=0;i<a.length;i++){
    heapInsert(a,i);
}

大根堆的调整heapIfy

堆中的一个数变小了，发生下沉调整的过程：

1.首先与两个子节点中较大值比较；当子节点存在比自己大的节点时，交换；并更新index；

2.重复步骤1，直到比子节点都大、或者不存在子节点时，停止

时间复杂度：logN,最多到叶节点的高度。

    static void heapify(int[] a,int index,int heapSize){
//        1.首先与两个子节点中较大值比较；当子节点存在比自己大的节点时，交换；并更新index；
//        2.重复步骤1，直到比子节点都大、或者不存在子节点时，停止
        int left=index*2+1;
        while(left<heapSize){
            int largest = left+1<heapSize&&a[left]<a[left+1]?left+1:left;
            if(a[index]<a[largest]){
                swap(a,index,largest);
                index=largest;
                left=index*2+1;
            }else break;
        }
    }

堆排序heapSort

取出堆顶的元素与最末尾交换，同时heapSize-1：

1.将大顶堆的堆顶和最后一个叶子节点交换（取出最大值，同时排到了数组的最后一个）

2.heapSize减一，同时调整变化后的大根堆，heapIfy的过程

时间复杂度：N*logN。重复N次heapIfy。

public static void heapSort(int[] a) {
    if(a==null||a.length<2) return;//数组为空为1位,直接返回
    for (int i = 0; i < a.length; i++) {
        heapInsert(a, i);       //将数组构建成大顶堆
    }
    int heapSize = a.length;    //初始化heapSize
    swap(a, 0, --heapSize);   //取出堆顶元素,与堆最后一个叶子节点元素交换
    while (heapSize > 0) {      //如果堆还有元素
        heapIfy(a, 0, heapSize);//调整堆
        swap(a, 0, --heapSize);//继续取出堆顶元素,与堆最后一个叶子节点元素交换
    }
}

堆的扩展（堆的结构和使用很重要）

什么是二叉堆？

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。
在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。
在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。

堆的相关知识

二叉堆的根节点叫作堆顶 。
最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素 。

堆的插入和删除操作，时间复杂度确实是O(logn)。但构建堆的时间复杂度却并不是O(nlogn)，而是O(n)。

二叉堆的存储结构：一般是用数组来存放的。

假设父节点的下标是parent，那么它的左孩子下标就是 2×parent+1 ；右孩子下标就是2×parent+2 。

一个节点的下标为i，它的父亲点下标为：（i-1）/2

优先队列

优先队列分为最大优先队列和最小优先队列。
在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的。
在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的。

当用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。