堆排序（Heap Sort）的详细实现与优化

一、问题描述
堆排序是一种基于二叉堆（完全二叉树）的排序算法，利用堆的最大堆/最小堆性质实现升序或降序排序。其核心思想是：

1. 将无序数组构建成一个堆（大顶堆用于升序排序）。
2. 重复将堆顶元素（最大值）与堆末尾元素交换，并调整堆结构，使剩余部分维持堆性质。
3. 时间复杂度为 O(n log n)，空间复杂度为 O(1)（原地排序）。

二、关键知识点：堆的性质

• 完全二叉树：所有层除最后一层外均满，最后一层节点靠左排列。
• 大顶堆：父节点值 ≥ 子节点值（根节点最大）。
• 节点关系：若父节点索引为 i，则左子节点为 2i+1，右子节点为 2i+2。

三、堆排序的逐步实现
步骤 1：构建初始大顶堆

• 从最后一个非叶子节点（索引 n/2 - 1）开始，向前依次对每个节点执行 堆化（Heapify）：
  • 比较当前节点与其子节点，若子节点更大，则交换父子节点。
  • 递归检查被交换的子节点是否满足堆性质（若交换后子节点可能破坏堆结构）。
• 示例：数组 [3, 7, 2, 11, 5]
  • 非叶子节点索引：5/2 - 1 = 1（节点值 7）→ 无需调整。
  • 索引 0（节点值 3）：与子节点 11 交换 → [11, 7, 2, 3, 5]，再检查节点 3（索引 3）无子节点，停止。

步骤 2：排序过程

1. 将堆顶元素（最大值 11）与末尾元素 5 交换 → [5, 7, 2, 3, 11]，此时末尾 11 已排序。
2. 对剩余未排序部分 [5, 7, 2, 3] 从根节点执行堆化：
   • 根节点 5 与子节点 7 交换 → [7, 5, 2, 3]，再检查节点 5（索引 1）无需调整。
3. 重复交换堆顶 7 与当前末尾 3 → [3, 5, 2, 7, 11]，再堆化 [3, 5, 2]：
   • 根节点 3 与子节点 5 交换 → [5, 3, 2]，检查节点 3（索引 1）无更大子节点，停止。
4. 继续交换堆顶 5 与末尾 2 → [2, 3, 5, 7, 11]，堆化 [2, 3] 后得 [3, 2]，最终交换得有序数组。

四、堆化操作的优化细节

• 递归堆化：

  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)  # 检查被交换的子节点  
  

• 迭代堆化：避免递归栈开销，通过循环向下调整。

五、完整堆排序代码（Python）

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)  # 对剩余部分堆化  
    return arr  

六、性能分析与优化

• 时间复杂度：
  • 建堆过程 O(n)（非叶子节点堆化总次数约为 n）。
  • n-1 次提取堆顶并堆化，每次 O(log n)，总排序 O(n log n)。
• 优化技巧：
  • 使用迭代代替递归减少栈空间。
  • 对于小规模数据，可结合插入排序优化常数因子。

七、总结
堆排序通过原地构建堆和反复调整堆结构实现高效排序，适用于数据流处理（如实时获取前k大元素）。重点掌握堆化操作与完全二叉树的索引关系，避免常见错误如忽略递归堆化或错误计算非叶子节点索引。