def heap_sort(array):
# 创建大顶二差堆 从最后一个非叶子节点(i=(length-1-1)//2) 开始到根节点(i=0)
for i in range((len(array) - 2) // 2, -1, -1):
down_adjust(i, len(array), array)
# 循环删除堆顶元素，替换到二插堆的末尾，调整堆产生新的堆顶
for i in range(len(array) - 1, 0, -1):
temp = array[i]
array[i] = array[0]
array[0] = temp
down_adjust(0, i, array)
def down_adjust(parent_index, length, array):
temp = array[parent_index]
child_index = parent_index * 2 + 1
while child_index < length:
if child_index + 1 < length and array[child_index + 1] > array[child_index]:
child_index += 1
if temp >= array[child_index]:
break
array[parent_index] = array[child_index]
parent_index = child_index
child_index = 2 * parent_index + 1
array[parent_index] = temp
my_array = [4, 9, 8, 7, 10, 5, 6, 3, 2]
heap_sort(my_array)
print(my_array)
