深入解析堆排序的算法思想及Java代码的实现演示
一、基础知识
我们通常所说的堆是指二叉堆,二叉堆又称完全二叉树或者叫近似完全二叉树。二叉堆又分为最大堆和最小堆。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。数组可以根据索引直接获取元素,时间复杂度为O(1),也就是常量,因此对于取值效率极高。
最大堆的特性如下:
- 父结点的键值总是大于或者等于任何一个子节点的键值
- 每个结点的左子树和右子树都是一个最大堆
最小堆的特性如下:
- 父结点的键值总是小于或者等于任何一个子节点的键值
- 每个结点的左子树和右子树都是一个最小堆
二、算法思想
1.最大堆的算法思想是:
先将初始的R[0…n-1]建立成最大堆,此时是无序堆,而堆顶是最大元素
再将堆顶R[0]和无序区的最后一个记录R[n-1]交换,由此得到新的无序区R[0…n-2]和有序区R[n-1],且满足R[0…n-2].keys ≤ R[n-1].key
由于交换后,前R[0…n-2]可能不满足最大堆的性质,因此再调整前R[0…n-2]为最大堆,直到只有R[0]最后一个元素才调整完成。
最大堆排序完成后,其实是升序序列,每次调整堆都是要得到最大的一个元素,然后与当前堆的最后一个元素交换,因此最后所得到的序列是升序序列。
2.最小堆的算法思想是:
先将初始的R[0…n-1]建立成最小堆,此时是无序堆,而堆顶元素是最小的元素
再将堆顶R[0]与无序区的最后一个R[n-1]交换,由此得到新的无序堆R[0…n-2]和有序堆R[n-1],且满足R[0…n-2].keys >= R[n-1].key
由于交换后,前R[0…n-2]可能不满足最小堆的性质,因此再调整前R[0…n-2]为最小堆,直到只有R[0]最后一个元素才调整完成
最小堆排序完成后,其实是降序序列,每次调整堆都是要得到最小的一个元素,然后与当前无序堆的最后一个元素交换,所以所得到的序列是降序的。
提示:堆排序的过程,其实就是不断地扩大有序区,然后不断地缩小无序区,直到只有有序区的过程。
三、排序过程分析
因为算法比较抽象,这里直接通过举个小例子来说明堆排序的过程是如何的。下面我们用这个无序序列采用最大堆的进行堆排序,所得到的序列就是升序序列(ASC)。
无序序列:89,-7,999,-89,7,0,-888,7,-7
第一步:初始化建成最大堆:
第二步:将堆顶最大元素999与无序区的最后一个元素交换,使999成为有序区。交换后,-7成为堆顶,由于-7并不是无序区中最大的元素,因此需要调整无序区,使无序区中最大值89成为堆顶,所以-7与89交换。交换后导致89的右子树不满足最大堆的性质,因此要对右子树调整成最大堆,所以-7要与0交换,如下图:
从图中看到,当-7成89交换后,堆顶是最大元素了,但是-7的左孩子是0,右孩子是-888,由于-7<0,导致-7这个结点不满足堆的性质,因此需要调整它。所以,0与-7交换。
然后不断重复着第二步的过程,直到全部成为有序区。
最后:所得到的是升序序列
四、时间复杂度
堆排序的时间,主要由建立初始堆和反复调整堆这两部分的时间开销构成.由于堆排序是不稳定的,它得扭到的时间复杂度会根据实际情况较大,因此只能取平均时间复杂度。
平均时间复杂度为:O( N * log2(N) )
堆排序耗时的操作有:初始堆 + 反复调整堆,时间复杂度如下:
1.初始建堆:每个父节点会和左右子节点进行最多2次比较和1次交换,所以复杂度跟父节点个数有关。根据2x <= n(x为n个元素可以折半的次数,也就是父节点个数),得出x = log2n。即O ( log2n )
2.反复调整堆:由于初始化堆过程中,会记录数组比较结果,所以堆排序对原序列的数组顺序并不敏感,最好情况和最坏情况差不多。需要抽取 n-1 次堆顶元素,每次取堆顶元素都需要重建堆(O(重建堆) < O(初始堆))。所以小于 O(n-1) * O(log2n)
使用建议:
由于初始化堆需要比较的次数较多,因此,堆排序比较适合于数据量非常大的场合(百万数据或更多)。由于高效的快速排序是基于递归实现的,所以在数据量非常大时会发生堆栈溢出错误。
五、Java示例代码
public class HeapSort{ private static int[] sort=new int[]{1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main(String[] args){ buildMaxHeapify(sort); heapSort(sort); print(sort); } private static void buildMaxHeapify(int[] data){ //没有子节点的才需要创建最大堆,从最后一个的父节点开始 int startIndex=getParentIndex(data.length-1); //从尾端开始创建最大堆,每次都是正确的堆 for(int i=startIndex;i>=0;i--){ maxHeapify(data,data.length,i); } } /** *创建最大堆 * *@paramdata *@paramheapSize需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了 *@paramindex当前需要创建最大堆的位置 */ private static void maxHeapify(int[] data,int heapSize,int index){ //当前点与左右子节点比较 int left=getChildLeftIndex(index); int right=getChildRightIndex(index); int largest=index; if(left<heapSize&&data[index]<data[left]){ largest=left; } if(right<heapSize&&data[largest]<data[right]){ largest=right; } //得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整 if(largest!=index){ int temp=data[index]; data[index]=data[largest]; data[largest]=temp; maxHeapify(data,heapSize,largest); } } /** *排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的 * *@paramdata */ private static void heapSort(int[] data){ //末尾与头交换,交换后调整最大堆 for(int i=data.length-1;i>0;i--){ int temp=data[0]; data[0]=data[i]; data[i]=temp; maxHeapify(data,i,0); } } /** *父节点位置 * *@paramcurrent *@return */ private static int getParentIndex(int current){ return(current-1)>>1; } /** *左子节点position注意括号,加法优先级更高 * *@paramcurrent *@return */ private static int getChildLeftIndex(int current){ return(current<<1)+1; } /** *右子节点position * *@paramcurrent *@return */ private static int getChildRightIndex(int current){ return(current<<1)+2; } private static void print(int[] data){ int pre=-2; for(int i=0;i<data.length;i++){ if(pre<(int)getLog(i+1)){ pre=(int)getLog(i+1); System.out.println(); } System.out.print(data[i]+"|"); } } /** *以2为底的对数 * *@paramparam *@return */ private static double getLog(double param){ return Math.log(param)/Math.log(2); } }