堆排序法的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 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[0], arr[i] = arr[i], arr[0]  # 交换
        heapify(arr, i, 0)

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("Sorted array is", arr)