用Python写一个堆排序代码含注释说明。

# 定义堆排序函数

def heap_sort(arr):

# 从最后一个非叶子节点开始构造初始堆

for i in range(len(arr) // 2 – 1, -1, -1):

heapify(arr, len(arr), i)

# 依次将堆顶元素和最后一个元素交换，并对前面的元素重新构造堆

for i in range(len(arr) – 1, 0, -1):

arr[0], arr[i] = arr[i], arr[0]

heapify(arr, i, 0)

# 定义堆化函数

def heapify(arr, n, i):

largest = i # 初始化最大值为父节点

l = 2 * i + 1 # 左子节点

r = 2 * i + 2 # 右子节点

# 找出最大值所在的节点

if l < n and arr[l] > arr[largest]:

largest = l

if r < n and arr[r] > arr[largest]:

largest = r

# 如果最大值不是父节点，则交换父节点和最大值所在节点的值，并递归地堆化下去

if largest != i:

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, n, largest)

下面我来写一个代码说明：

1. 定义heap_sort函数，参数为待排序的列表arr。
2. 从最后一个非叶子节点开始，逐个构造初始堆，即调用heapify函数。
3. 依次将堆顶元素和最后一个元素交换，并对前面的元素重新构造堆，即循环调用heapify函数。
4. 定义heapify函数，参数为待堆化的列表arr、列表长度n和父节点的索引i。
5. 初始化最大值为父节点的索引。
6. 找出左右子节点中最大值所在的节点。
7. 如果最大值不是父节点，则交换父节点和最大值所在节点的值，并递归地堆化下去，即调用heapify函数。