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
优先队列
优先队列分为最大优先队列和最小优先队列。
在最大优先队列中,无论入队顺序如何,当前最大的元素都会优先出队,这是基于最大堆实现的。
在最小优先队列中,无论入队顺序如何,当前最小的元素都会优先出队,这是基于最小堆实现的。
当用最大堆来实现最大优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。