Python全系列 教程
3567个小节阅读:5931k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
为了维护堆的特性,有如下2种操作
比如此图
这样看我们的图也破坏了小根堆的平衡性对吧,我们需要向上走,首先看左下方的小子树,找到最小的并往上走,变成子树的根节点。
我们继续变换右图方块中的子树。
最终我们经过几次变换,就又成为了一个小根堆。
假设说我们现在把根节点的2改为100,那么就打破了我们堆得定义,就不是一个小根堆了,为了让它构成一个小根堆,我么需要让做一些操作来让它变回小根堆。那么就需要去变换一下。
更改后发现其实还是满足不了小根堆的定义,因为第二层的右子树并不满足小根堆的定义,我们继续来转换。
后改变方块圈出来的位置,就完成了最后down的操作,重新变回了小根堆。
xxxxxxxxxx
def 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)