堆排序（Heap Sort）

# /*
# 堆排序（Heap Sort）
# --------------------------------------------------------
# 原理：
# 利用“堆”这种完全二叉树结构进行排序。
# 通过将序列构造成最大堆（或最小堆），
# 不断取出堆顶元素并重建堆，最终得到有序序列。
#
# 堆排序属于原地排序，空间占用小，性能稳定。
# */

# 构建最大堆的调整函数
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)


# 堆排序主函数
def heap_sort(arr):
    n = len(arr)

    # 1) 构建最大堆（从最后一个非叶子结点开始）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2) 将堆顶元素依次换到序列末尾，并重新调整堆
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # 将最大值放到末尾
        heapify(arr, i, 0)                # 重建堆，范围缩小

    return arr


# 示例演示
data = [12, 11, 13, 5, 6, 7]
print("排序前：", data)
result = heap_sort(data)
print("排序后：", result)

# --------------------------------------------------------
# 关键要点总结：
# 1) 利用完全二叉树“堆结构”进行排序；
# 2) 最大堆适合升序排序，最小堆适合降序排序；
# 3) 构建堆 O(n)，排序过程中每次调整 O(log n)；
# 4) 总体时间复杂度 O(n log n)；
# 5) 空间复杂度 O(1)，属于“原地排序”；
# 6) 不稳定排序；
# 7) 在需要空间节省时非常实用。
# */
#
# 排序前： [12, 11, 13, 5, 6, 7]
# 排序后： [5, 6, 7, 11, 12, 13]