用python写一个堆排序

堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为O(nlogn)。下面是用Python实现堆排序的代码：

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)


def heap_sort(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)

在上面的代码中，`heapify`函数用于将以`i`为根节点的子树堆化，`heap_sort`函数用于对数组进行堆排序。首先在`heap_sort`函数中构建一个最大堆，然后一个个取出最大值并放到数组末尾，最后得到一个有序的数组。