堆排序
堆排序是基于比较的 二进制堆数据结构允许堆排序算法利用堆的
堆数据结构
的
节点的父节点、左子节点和右子节点可以表示为
有两种二进制堆: Max-heap属性: 最小堆属性: min-heap和max-heap都可以用于实现堆排序,但本wiki将从max-heap的角度讨论堆排序。要转换为min-heap,只需将问题改为使用min-heap,并确保min-heap属性保持不变。
显示数组 我们有一个max-heap
但我们可以看到这里不是这样,因为
如果
类似地,如果
维护Max-heap
为了维护max-heap属性,堆排序使用一个名为
下面是一个Python实现
1 2 3 4 5 6 7 8 9 10 11 |
|
本质上,如果一个元素
堆排序算法
堆排序算法有两个主要部分(将在下面进一步分解):构建max-heap,然后对其排序。max-heap的构建方法如上一节所述。然后,通过反复从堆中移除最大的元素(即堆的根),然后将其插入到数组中,堆排序生成一个已排序的数组。每次移除后都会更新堆。一旦所有元素都从堆中移除,结果就是一个排序的数组。
堆排序算法使用
- 从无序数组构建max-heap。
- 找到最大元素,它位于
- 交换元素
- 将堆大小减1(这将丢弃我们刚刚移动到堆底部的节点,它是最大的元素)。从某种意义上说,列表中排序的部分增加了,而堆(包含未排序的元素)缩小了。
- 现在运行
max_heapify 在堆上,以防新根导致违反max-heap属性。(它的子节点仍然是max-heap。) - 返回步骤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-heap需要 注:虽然这是事实 堆排序的运行时间为 堆排序的最坏情况和平均情况运行时间为
利与弊
优点
- 的时间效率和时间复杂度
- 较少的内存使用
- 稳定的性能:它在最佳、平均和最坏情况下的性能都一样好
缺点
- 不稳定排序
- 外部排序不可能与堆排序
另请参阅
参考文献
- ,年代。
堆排序的例子 .检索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