本文主要介绍堆排序的一些基本过程和分析。
大纲
- 堆排序简介
- 堆排序代码实现
1. 堆排序简介
1.1 堆排序的存储
一般用数组表示堆，若根结点存在序号0处， i结点的父结点下标就为。
结点的左右子结点下标分别为
和
。（注：如果根结点是从1开始，则左右孩子结点分别是
和
。）
1.2 堆排序的过程
想要清楚堆排序的过程，首先需要明白两个问题：
- 如何由一个无序序列建成一个堆？
- 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
如何由一个无序序列建成一个堆？
用数组存储序列，那么初始状态如下图：
初始状态
接下来我们需要对初始状态做调整，假设我们创建最小堆，那么从最后一个非叶子节点开始进行调整，使得以该节点为根节点的子树满足最小堆的要求；直到调整到根节点。
由于节点的左右节点分别为
和
,最开始从倒数的第一个非叶子节点开始调整，因此该节点为
；直到调整到节点0，完成最开始的调整。
如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
一般在输出堆顶元素之后，视为将这个元素排除，然后用表中的最后一个元素填补它的位置，自下向上调整：首先，将堆顶元素和它的左右子树的根节点进行比较，把最小的元素交换到堆顶；然后，顺着被破坏的路径一路调整下去，直至叶子节点，就得到新的堆。我们称这个自堆顶至叶子的调整过程为“筛选”。重复这个过程，直到完成排序；该过程的每一次调整都是从根节点开始调整。
1.3 复杂度分析
堆排序方法对记录数较少的文件并不值得提倡，但对较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。因此，堆排序的时间复杂度分两个部分。
初始化建堆是从第一个非叶子节点开始的，因此所有的叶子节点是不需要调整的，而需调整节点是与它们的子节点以及子树相比较。那么每一层的时间复杂度为,其中
表示第
层上的节点个数，
表示树的深度，
表示要比较的次数。
所以，总的时间复杂度为：
等式的求解，等式左右乘上2，然后和原来的等式相减，可以得到：
根据等比数列的求和公式：
最终得到：
因为堆排序为完全二叉树，因此。所以
,初始化建堆的时间复杂度就是
.
重新调整的过程是顶点节点与其子树调整，循环次，每次调整的次数最多
，因此该部分的事件复杂度为
.
综上分析，堆排序的时间复杂度是。而且，堆排序在最坏的情况下，其时间复杂度也为
。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。
2. 堆排序代码实现
def sift_down(arr, start, end):
root = start
while True:
# 从root开始对最大堆调整
child = 2 * root + 1
if child > end:
break
# 找出两个child中交大的一个
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
# 最大堆小于较大的child, 交换顺序
arr[root], arr[child] = arr[child], arr[root]
# 正在调整的节点设置为root
root = child
else:
# 无需调整的时候, 退出
break
def heap_sort(arr):
# 从最后一个有子节点的孩子开始调整最大堆
# 每次调整以该节点为start节点，也就是说调整的是该节点的子树。
first = len(arr) // 2 - 1
for start in range(first, -1, -1):
sift_down(arr, start, len(arr) - 1)
# 将最大的放到堆的最后一个, 堆-1, 继续调整排序
for end in range(len(arr) -1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(arr, 0, end - 1)
def main():
# [7, 95, 73, 65, 60, 77, 28, 62, 43]
# [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
print l
heap_sort(l)
print l
if __name__ == "__main__":
main()
网友评论