堆排序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 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)

    return arr

在堆排序中，heapify()函数用于维护堆的性质，heap_sort()函数用于构建堆并进行排序。首先，heap_sort()函数在数组中构建一个最大堆。然后，它从最后一个元素开始，将其与堆顶元素交换，并再次调用heapify()函数以维护堆的性质。重复这个步骤，直到整个数组按升序排列。