如何使用Python实现堆排序函数

堆排序是一种排序算法，通过构建最大堆（或最小堆）来实现排序。下面是使用Python实现堆排序函数的示例代码：

def heapify(arr, n, i):
    largest = i      # 将最大元素的索引初始化为根节点
    left = 2 * i + 1 # 左子节点的索引
    right = 2 * i + 2 # 右子节点的索引
 
    # 如果左子节点存在且大于根节点，则将最大元素的索引更新为左子节点
    if left < n and arr[i] < arr[left]:
        largest = left
 
    # 如果右子节点存在且大于根节点和左子节点，则将最大元素的索引更新为右子节点
    if right < n and arr[largest] < arr[right]:
        largest = right
 
    # 如果最大元素的索引不是根节点的索引，则交换它们，并递归对被交换的子节点进行堆化
    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)
print("排序后的数组为：")
for i in range(len(arr)):
    print("%d" % arr[i])

上述代码中的heapify函数用于将以特定节点为根的子树（二叉树）堆化，heapSort函数用于实现堆排序的主要逻辑。堆排序过程分为两个步骤：

1. 初始时，先构建最大堆，然后将最大的元素（堆顶元素）与当前未排序部分的最后一个元素交换，并重新堆化剩余的元素，即将次大的元素放到倒数第二个位置。

2. 重复上述过程，直到堆为空，最后得到的数组为有序的。

通过上述实现，我们可以使用Python实现堆排序函数。这种算法的时间复杂度为O(nlogn)，空间复杂度为O(1)。