堆排序是一种高效的排序算法，它利用了堆（Heap）这种数据结构的特性。堆是一个完全二叉树，且满足父节点的值大于等于（最大堆）或小于等于（最小堆）其子节点的值。堆排序通过反复提取堆顶元素（最大值）并调整堆，最终得到有序数组，时间复杂度稳定为O(n log n)，适合大规模数据排序。

堆的结构与索引关系¶

堆在数组中可以用完全二叉树表示，若数组索引从0开始：
- 父节点索引为i时，左子节点索引为2i + 1，右子节点索引为2i + 2；
- 子节点索引为j时，父节点索引为(j - 1) // 2。

核心操作1：调整堆（Heapify）¶

调整堆的作用是将以节点i为根的子树调整为最大堆。步骤如下：
1. 初始化当前节点i为最大值位置；
2. 比较i的左右子节点，找出最大值的子节点索引；
3. 若最大值子节点大于当前节点，交换两者，并递归调整被交换的子节点。

def heapify(arr, n, i):
    largest = i  # 假设当前节点是最大值
    left = 2 * i + 1
    right = 2 * i + 2

    # 若左子节点更大，更新最大值位置
    if left < n and arr[left] > arr[largest]:
        largest = left
    # 若右子节点更大，更新最大值位置
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 若最大值不是当前节点，交换并递归调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

核心操作2：构建最大堆¶

构建最大堆需从最后一个非叶子节点开始，逐步向上调整每个节点，确保整个数组满足最大堆性质。最后一个非叶子节点的索引为n // 2 - 1（n为数组长度）。

def build_max_heap(arr):
    n = len(arr)
    # 从最后一个非叶子节点开始向上调整
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

堆排序主函数¶

堆排序的逻辑是：先构建最大堆，再反复交换堆顶元素与堆尾元素，同时调整堆以维持最大堆性质，最终得到有序数组。

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)  # 构建最大堆

    # 逐个提取堆顶元素（最大值）并调整堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换堆顶与当前末尾元素
        heapify(arr, i, 0)  # 调整剩余元素为最大堆
    return arr

示例演示¶

以数组[12, 11, 13, 5, 6, 7]为例：
1. 构建最大堆：
初始数组：[12, 11, 13, 5, 6, 7]
从最后一个非叶子节点（索引2，值13）开始调整，逐步向上处理，最终得到最大堆：[13, 12, 11, 5, 6, 7]。

2. 提取最大值并调整：
   - 交换堆顶（13）与末尾元素（7），数组变为[7, 12, 11, 5, 6, 13]，调整堆后得到[12, 7, 11, 5, 6, 13]；
   - 重复交换堆顶与末尾元素，最终数组变为[5, 6, 7, 11, 12, 13]。

总结¶

堆排序通过构建最大堆和调整堆实现高效排序，核心是理解堆的结构和调整逻辑。Python实现中，heapify函数是关键，它确保堆的性质，而build_max_heap和heap_sort函数则串联起整个排序流程。堆排序是原地排序，空间复杂度为O(1)，时间复杂度为O(n log n)，适用于大数据量场景。