⭐ 题目日期：

金山 - 2024/12/31

📝 题解：

堆排序是一种基于二叉堆数据结构的比较排序算法，其过程分为构建最大堆和排序两个阶段。以下是详细步骤：

1. 构建最大堆

• 目标：将无序数组调整为最大堆，即每个节点的值大于或等于其子节点的值。

• 步骤：

  1. 确定最后一个非叶子节点：索引为 ( \frac{n}{2} - 1 )（数组从0开始）。
  2. 从后往前调整：对每个非叶子节点执行下沉操作（Heapify），确保其子树满足最大堆性质。
  3. 下沉操作：比较当前节点与左右子节点，若子节点更大则交换，并递归调整交换后的子树。

  示例：数组 [3, 1, 4, 1, 5, 9, 2, 6]

  • 最后一个非叶子节点索引为 ( 8/2 - 1 = 3 )（元素1）。
  • 依次调整索引3→2→1→0的节点，最终得到最大堆 [9, 6, 4, 5, 1, 3, 2, 1]。

---

2. 排序阶段

• 目标：通过反复移除堆顶元素（最大值）并调整堆，实现升序排序。

• 步骤：

  1. 交换堆顶与末尾元素：将最大值移至数组末尾。
  2. 缩小堆范围：堆大小减1，排除已排序的末尾元素。
  3. 调整堆顶：对新的堆顶元素执行下沉操作，恢复最大堆性质。
  4. 重复上述步骤：直到堆大小为1，数组完全有序。

  示例（续前例）：

  • 第一次交换后数组为 [1, 6, 4, 5, 1, 3, 2, 9]，调整前7个元素得到新堆 [6, 5, 4, 1, 1, 3, 2]。
  • 重复交换与调整，最终得到有序数组 [1, 1, 2, 3, 4, 5, 6, 9]。

---

关键点

• 时间复杂度：构建堆 ( O(n) )，每次调整 ( O(\log n) )，总时间 ( O(n \log n) )。
• 空间复杂度：原地排序，( O(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)

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[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

通过上述步骤，堆排序高效地将无序数组变为有序，尤其适用于大数据量的场景。