def heap_sort(arr):

n = len(arr)

# 构建大顶堆，从最后一个非叶子节点开始，从右往左依次构建大顶堆
for i in range(n//2-1, -1, -1):
    adjust_heap(arr, i, n)

# 将最大的元素与未排序的数组的末尾元素交换，将最大元素放到数组末尾，然后重新调整剩余元素为大顶堆
for j in range(n-1, 0, -1):
    arr[0], arr[j] = arr[j], arr[0]  # 交换元素位置
    adjust_heap(arr, 0 , j)  # 重新调整剩余元素为大顶堆

return arr

    

def adjust_heap(arr, i , length):

left = 2 * i + 1   # 左子树的序号 也是当前节点i的左孩子节点序号 也是当前i序号在list中实际位置*2+1得到左孩子在list中实际位置  
right = 2 * i + 2   # 右子树的序号 也是当前i序号在list中实际位