堆排序（Heap Sort）

题目描述：给定一个整数数组，使用堆排序算法将其按升序排列。堆排序是一种基于二叉堆数据结构的比较排序算法，具有O(n log n)的时间复杂度，且是原地排序（只需要常数级别的额外空间）。

解题过程：

1. 理解堆结构
   首先需要理解二叉堆（通常指最大堆）的性质：

• 是一个完全二叉树
• 每个节点的值都大于或等于其子节点的值（最大堆特性）
• 可以用数组来表示：对于位置i的节点，其左子节点在2i+1，右子节点在2i+2，父节点在⌊(i-1)/2⌋

2. 构建最大堆
   从最后一个非叶子节点开始（位置⌊n/2⌋-1），向前遍历到根节点，对每个节点执行堆化操作：

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)

3. 排序过程
   构建好最大堆后，根节点是最大值。排序步骤：

• 将根节点（最大值）与最后一个元素交换
• 堆的大小减1（排除已排序的最大值）
• 对新的根节点执行堆化，恢复最大堆性质
• 重复直到堆大小为1

完整实现：

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 = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后:", arr)  # 输出: [5, 6, 7, 11, 12, 13]

4. 关键点说明

• 堆化操作的时间复杂度是O(log n)
• 构建堆的时间复杂度是O(n)（看似是O(n log n)，但通过数学分析可得是O(n)）
• 总体时间复杂度为O(n log n)
• 是不稳定排序（相同元素可能改变相对顺序）
• 只需要常数额外空间，是原地排序

5. 性能优化

• 对于小规模数据，堆排序的常数因子较大，不如插入排序高效
• 在实际应用中常与其他算法结合使用（如内省排序）