堆排序（只调整变化的子树）
"""
堆排序：
从后向前找第一个非叶子节点，构造初始的大根堆
将堆顶元素进行交换后，重新从堆顶开始进行重构大根堆
"""
# 构造大根堆的函数
def
ConsHeap(arr
,n
,i
):
# 递归对变换了根位置的子树进行调整
large
= i # 将当前索引当作最大索引
# 计算左右子树
left
= 2 * i
+ 1
right
= 2 * i
+ 2
# 如果左孩子存在，并且左孩子比父节点大，移动最大索引
if left
< n and arr
[left
] > arr
[i
]:
large
= left
# 如果右孩子存在，并且比最大的索引值大，移动最大索引
if right
< n and arr
[right
] > arr
[large
]:
large
= right
# 如果large的位置发生了变化，不是当前根节点
if i
!= large
:
# 交换位置
,将最大值放到根节点位置
arr
[i
],arr
[large
] = arr
[large
],arr
[i
]
# 对发生了变化的子树进行调整
ConsHeap(arr
,n
,large
)
def
HeapSort(arr
):
# 进行堆排序
n
= len(arr
)
# 首先构造原始数组的大根堆
,从后向前遍历寻找第一个非叶子节点，调整其父子节点的关系
for i
in range(n
-1,-1,-1):
ConsHeap(arr
,n
,i
)
# 将堆顶元素与末尾元素互换，重新从堆顶开始构造大根堆
for i
in range(n
-1,0,-1): # 直到只剩下一个元素为止
# 互换堆顶与末尾元素
arr
[0],arr
[i
] = arr
[i
],arr
[0]
# 重新调整大根堆
ConsHeap(arr
,i
,0)
return arr
if __name__
== '__main__':
a
= [1,8,7,9,45,145,1,7,8,656,4,100,9]
print(HeapSort(a
)) # mmp
,低级编写错误，还是debug好用
