简介
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
特点
- 堆:一种特殊的完全二叉树结构
- 大根堆:一棵完全二叉树,满足任一节点都比其孩子节点大
- 小根堆:一棵完全二叉树,满足任一节点都比其孩子节点小
堆排序节点访问
在这里我们借用wiki的定义来说明:
通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中
父节点i的左子节点在位置:(2*i+1);
父节点i的右子节点在位置:(2*i+2);
子节点i的父节点在位置:(i-1)//2;
执行步骤
- 构建堆:将待排序序列构建成一个堆 H[0……n-1],从最后一个非叶子结点开始,从左至右,从下至上进行调整。根据升序或降序需求选择大顶堆或小顶堆;
- 此时的堆顶元素,为最大或者最小元素;
- 把堆顶元素和堆尾元素互换,调整堆,重新使堆有序;
- 此时堆顶元素为第二大元素;
- 重复以上步骤,直到堆变空。
动图演示
实例代码
####
# 今日头条:技术好奇心
####
# 构建维护堆
def heapify(arr, n, i):
# 最大位置
largest = i
# left = 2*i + 1
l = 2 * i + 1
# right = 2*i + 2
r = 2 * i + 2
# 比较父节点与左孩子大小
if l < n and arr[i] < arr[l]:
largest = l
# 比较右孩子与目前的大节点值大小
# (目前可能是父亲也可能是左孩子)
if r < n and arr[largest] < arr[r]:
largest = r
# 检查上面步骤得出的最大值是否是最初上面定义的父节点
# 如果不是,则进行交换和递归
if largest != i:
# 交换
arr[i], arr[largest] = arr[largest], arr[i]
# 递归对子树作出调整
heapify(arr, n, largest)
# 堆排序
def heap_sort(arr):
# 数组长度
n = len(arr)
# 构建大顶堆,由下往上构建所以用-1
for i in range(n, -1, -1):
heapify(arr, n, i)
print('--------- 构建之后的数组内容 ----------')
print(arr)
# 一个个交换元素
for i in range(n - 1, 0, -1):
# 交换
arr[i], arr[0] = arr[0], arr[i]
# 维护交换后的堆
heapify(arr, i, 0)
if __name__ == "__main__":
print('今日头条:技术好奇心')
print('----------- 排序前数组内容 -----------------')
arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
print(arr)
heap_sort(arr)
print('------------ 排序后的结果 ------------------')
print(arr)
运行结果:
今日头条:技术好奇心
----------- 排序前数组内容 -----------------
[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
------------ 排序后的结果 ------------------
[1, 2, 3, 7, 17, 19, 25, 26, 36, 90]