内容简介:我们在介绍《什么是优先队列》的时候就注意到,如果每次都删除堆顶元素,那么将会得到一个有序的数据。因此,我们可以利用二叉堆来对数据进行排序。通过前面的学习我们可以看到,如果构建一个二叉堆,最后每次从堆顶取出一个元素,那么最终取出元素就是有序的,不过如果要用来对数据按照从小到大排序,就不是构造小顶堆,而是大顶堆了,即堆顶元素大于等于其左右儿子节点。总结堆排序思路如下:根据前面的分析,我们来看一个具体的例子。假设我们要对
我们在介绍《什么是优先队列》的时候就注意到,如果每次都删除堆顶元素,那么将会得到一个有序的数据。因此,我们可以利用二叉堆来对数据进行排序。 点我查看本文代码地址。
堆 排序 分析
通过前面的学习我们可以看到,如果构建一个二叉堆,最后每次从堆顶取出一个元素,那么最终取出元素就是有序的,不过如果要用来对数据按照从小到大排序,就不是构造小顶堆,而是大顶堆了,即堆顶元素大于等于其左右儿子节点。总结堆排序思路如下:
- 以O(N)时间复杂度构建N个元素的二叉堆
- 以O(logN)时间复杂度删除一个堆顶元素,N个元素时间复杂度为O(NlogN)
- 由于删除一个堆顶元素时,就会空出一个位置,为了节省空间,将删除的堆顶元素放到数组末尾
- 当堆为空时,完成排序
- 由于数组元素从下标0开始,因此每个位置必须利用好。假设堆顶元素位置为i,那么左右儿子节点位置分别为2i+1,2i+2
实例分析
根据前面的分析,我们来看一个具体的例子。假设我们要对
进行排序。
该数据构成的原始二叉树如下:
构建二叉堆
为了能够使得数组所有元素满足堆的性质,即父节点大于等于儿子节点,我们需要从倒数第二层开始调整(为什么不是从最后一层?)。即调整8和10。
对于8来说,找到它的儿子节点中较大的一个,即35,将8和35交换后如下:
此时数组数据为:
对于10来说,它比左右儿子节点都大,因此不需要调整。
对于1来说,它的右儿子35最大,因此需要调整,和右儿子交换后如下:
此时数组数据为:
但是一次交换后,我们发现,1的左儿子还是比它大,因此交换它和较大的左儿子的位置,交换后如下:
此时数组数据为:
最终我们得到了满足堆性质的二叉堆了。
基于二叉堆的排序
在堆创建好后,每次取出堆顶元素,并且调整堆,把堆顶元素放在数组最后即可。
例如,对于前面创建好的堆,堆顶元素是35,我们取出第i(此时为1)个元素35,并把堆最后一个元素放在数组倒数第i个位置:
为了满足堆性质,我们需要调整堆顶元素,因为堆顶元素目前不满足堆性质,因此需要交换8和15的位置:
此时所有元素再次满足堆性质。
此时数组数据为:
对于其他元素也是同样的操作,因此不再赘述。
代码实现
根据上面的分析,关键代码实现如下:
void adjust_ele(ElementType arr[],int i,int length) { int child ; ElementType temp; for(temp = arr[i];2*i+1 < length;i = child) { child = 2 * i +1; /*找到较大的儿子*/ if(child != length-1 && arr[child+1] > arr[child]) child+=1; /*如果空穴元素小于该儿子,则空穴下滑*/ if(temp < arr[child]) arr[i] = arr[child]; else break; } /*将i位置的元素放到正确的位置*/ arr[i] = temp; } void heap_sort(ElementType arr[],int length) { int i = 0; /*构建堆*/ for(i = length /2;i >= 0;i--) { adjust_ele(arr,i,length); //printArr(arr,length); } for(i = length-1;i > 0;i--) { /*填充i位置的空穴*/ swap(&arr[0],&arr[i]); /*每次都处理堆顶元素*/ adjust_ele(arr,0,i); //printArr(arr,length); } }
完整可运行代码地址: heapSort
运行结果:
before sort:1 10 8 5 7 15 35 after sort:1 5 7 8 10 15 35
总结
结合我们前面介绍的优先队列,我们很容易理解堆排序,不过需要注意的就是位置0必须使用上。另外通过利用删除堆顶元素后空出来的位置,避免了另外申请数组内存来存放排序好的数组。建议自己修改完整可运行代码,来观察数据调整情况。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 图解排序算法
- 算法图解阅读笔记-选择排序
- 【图解数据结构】 归并排序
- 【图解数据结构】 一组动画演示选择排序
- 数据结构常见的八大排序算法及代码实现图解
- 图解集合 3 : CopyOnWriteArrayList
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。