堆排序算法
原创
堆排序算法是一个基于完全二叉树形结构的排序算法。二叉树是需要抽象出来的，只是为了方便来理解排序的过程。
堆排序算法有大根堆和小根堆， 这里我们以大根堆为例。对于堆排序来说，存在这样的特性根节点大于等于他的孩子节点。
对于一个数组来说，怎么看成是一颗二叉树呢。数组是把二叉树每一层遍历后存储的一种形式。
1.抽象出二叉树
对于数组6， 7， 4， 3，8的树形结构可以表示如下。对于任何一个元素的下标i， 左孩子是2*（i+1）-1 下标所在的位置， 右孩子是 2*（i+1）所在的位置。
堆排序算法
数组的二叉树形式
2.建立大根堆
建立的堆就是这样的形式，根节点大于左右孩子。很显然数组第一个算法是最大值所在的位置。
堆排序算法
大根堆
3.排序提取堆顶元素
排序过程，把对最大元素8与数组的最后一个元素调换位置，这个时候8就来到了数组的最后位置，6就来到了数组的第一个元素。
堆排序算法
8放到最后位置，并且固定
最后那个位置需要固定住，是我们找到的第一个最大元素。
4.重新调整堆
这个时候发现堆的条件不成立了，重新调整堆的结构。
堆排序算法
重新调整后的堆的结构
5.再次提取堆顶元素，重复3-4的过程
看一下python实现的堆排序代码：
def heap_adjust(elements, i, n):
l = 2 * (i + 1) - 1
r = 2 * (i + 1)
k = i
if r >= n or l >= n:
return
if elements[l] < elements[r]:
k = r
elif elements[l] > elements[r]:
k = l
if elements[i] < elements[k]:
elements[i], elements[k] = elements[k], elements[i]
heap_adjust(elements, k, n)
def heap_sort(elements):
n = len(elements)
for i in range(int(n / 2), -1, -1):
heap_adjust(elements, i, n)
for i in range(n - 1, -1, -1):
elements[i], elements[0] = elements[0], elements[i]
heap_adjust(elements, 0, i)
if __name__ == '__main__':
arr = [6, 7, 4, 3, 8]
heap_sort(arr)
print(arr)运行结果：
[3, 4, 6, 7, 8]
更多内容请关注公众号：IT技术漫漫谈
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
腾讯云开发者
