python 堆排序代码

以下是 python 实现堆排序的代码：

def heapify(arr, n, i):
    largest = i  # 初始化最大元素为根节点
    l = 2 * i + 1  # 左子节点
    r = 2 * i + 2  # 右子节点
 
    # 如果左子节点比根节点大，则更新最大元素
    if l < n and arr[i] < arr[l]:
        largest = l
 
    # 如果右子节点比最大元素大，则更新最大元素
    if r < n and arr[largest] < arr[r]:
        largest = r
 
    # 如果最大元素不是根节点，则交换根节点和最大元素
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
 
        # 递归地堆化子树
        heapify(arr, n, largest)
 
 
def heapSort(arr):
    n = len(arr)
 
    # 建立最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
 
    # 一个个从堆中取出元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)

使用以下代码进行测试：

arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("排序后的数组：")
for i in range(n):
    print("%d" % arr[i])

输出结果如下：

排序后的数组：
5
6
7
11
12
13