小堆排序python

小堆排序是一种基于堆数据结构的排序算法，它通过构建小顶堆来实现排序。下面是小堆排序的Python实现：

def heapify(arr, n, i):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] > arr[left]:
        smallest = left

    if right < n and arr[smallest] > arr[right]:
        smallest = right

    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify(arr, n, smallest)

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)

    return arr

在这个实现中，`heapify`函数用于维护小顶堆的性质，`heapSort`函数则用于进行排序。首先，`heapSort`函数通过调用`heapify`函数构建初始的小顶堆。然后，它通过不断交换堆顶元素和最后一个元素，并调用`heapify`函数来重新构建小顶堆，实现排序。