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

优先队列

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

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