目录Python全系列 教程
3567个小节阅读：5930.6k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
为了维护堆的特性，有如下2种操作
比如此图
这样看我们的图也破坏了小根堆的平衡性对吧，我们需要向上走，首先看左下方的小子树，找到最小的并往上走，变成子树的根节点。
我们继续变换右图方块中的子树。
最终我们经过几次变换，就又成为了一个小根堆。
假设说我们现在把根节点的2改为100，那么就打破了我们堆得定义，就不是一个小根堆了，为了让它构成一个小根堆，我么需要让做一些操作来让它变回小根堆。那么就需要去变换一下。
更改后发现其实还是满足不了小根堆的定义，因为第二层的右子树并不满足小根堆的定义，我们继续来转换。
后改变方块圈出来的位置，就完成了最后down的操作，重新变回了小根堆。
xxxxxxxxxxdef down(heap:list[int],index:int,size:int): ''' 维护堆的特性 ''' # 建立一个变更，来存储最大值的索引 max_index = index # 获取左节点的索引 left = max_index * 2 + 1 # 获取右节点的索引 right = max_index *2 + 2 # 进行比较获取出最大值索引来 if left < size and heap[max_index] < heap[left]: max_index = left if right < size and heap[max_index] < heap[right]: max_index = right # 如果max_index 和 index 值不一样，说明需要进行交换 if max_index != index: heap[max_index],heap[index] = heap[index],heap[max_index] down(heap,max_index,size)
def heap_sort(heap:list[int]): # 获取堆有多少数据 size = len(heap) # 打印原始数据 print(heap) # 建堆 for i in range(size//2,-1,-1): # 为了保证一次性取到最大值，所以让索引倒取 down(heap,i,size) # 打印维护后数据 print(heap) # 排序 for i in range(size-1,0,-1): # 将最大值和未排序的最一个索引进行交换 heap[i],heap[0] = heap[0],heap[i] # 维护堆的特性 down(heap,0,i) print(heap)
if __name__ == "__main__": heap = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] heap_sort(heap)