堆排序
堆排序是基于比较的 二进制堆数据结构允许堆排序算法利用堆的数据结构
堆数据结构
的
节点的父节点、左子节点和右子节点可以表示为
二进制堆有两种类型: Max-heap属性: 最小堆属性: 最小堆和最大堆都可以用来实现堆排序,但本wiki将从最大堆的角度来讨论堆排序。要转换为最小堆,只需将问题改为使用最小堆,并确保最小堆属性有效。
显示数组 我们有一个最大堆
但我们可以看到这里不是这样,因为
如果
类似地,如果
维护一个Max-heap
为了维护max-heap属性,堆排序使用一个名为
这是一个Python实现
1 2 3 4 5 6 7 8 9 10 11 |
|
本质上,如果一个元素
堆排序算法
堆排序算法有两个主要部分(下面将进一步细分):构建一个最大堆,然后对其排序。按照上一节的描述构建max堆。然后,通过反复删除堆中最大的元素(即堆的根),然后将其插入数组,heapsort生成一个排序数组。堆在每次移除后更新。一旦所有元素都从堆中移除,结果就是一个排序的数组。
堆排序算法使用
- 从一个无序数组构建一个最大堆。
- 求最大元素,其位于
- 交换元素
- 将堆大小减1(这将丢弃我们刚刚移动到堆底部的节点,它是最大的元素)。从某种意义上说,列表中排序的部分增长了,而堆(存放未排序元素的堆)收缩了。
- 现在运行
max_heapify 以防止新的根目录违反max-heap属性。(它的子节点仍然是max-heaps。) - 返回到步骤2。
堆排序的实现
下面是一个堆排序算法的Python实现。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
堆排序的复杂性
堆排序的运行时间为 从无序列表构建max堆需要 注意:虽然这是真的 堆排序的运行时间为 堆排序的最坏情况和平均情况的运行时间为
优点和缺点
优点
- 时间效率高,时间复杂度高
- 减少内存使用
- 一致性性能:它在最佳、平均和最坏情况下都表现得一样好
缺点
- 不稳定排序
- 外部排序不可能与堆排序
另请参阅
参考文献
- ,年代。
堆排序的例子 .2016年6月7日检索自https://en.wikipedia.org/wiki/File:Heapsort-example.gif - Demaine, E, & Devadas, S。
第4讲:堆和堆排序 .2016年5月23日检索自http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec04.pdf