堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的比较排序算法。它的执行过程可以分为两个主要阶段：建堆（Heapify）和排序（Sorting）。下面详细解释堆排序的执行过程。
1. 堆的基本概念
- 二叉堆：一种完全二叉树，满足堆性质：最大堆：每个父节点的值大于或等于其子节点的值。最小堆：每个父节点的值小于或等于其子节点的值。
- 堆的存储：通常用数组表示，对于节点 i：左子节点：2i + 1右子节点：2i + 2父节点：(i - 1)/2
2. 堆排序的步骤
阶段一：建堆（Heapify）
将无序数组构建成一个堆（通常为最大堆）。
- 从最后一个非叶子节点开始调整：
- 最后一个非叶子节点的索引为 n/2 - 1（n 是数组长度）。
- 从该节点开始，依次向前调整每个子树，使其满足堆性质。
- 调整方法（Sift Down）：
- 比较当前节点与其左右子节点的值。
- 如果当前节点小于某个子节点（最大堆），则交换它们。
- 递归调整被交换的子节点，直到当前节点满足堆性质。
阶段二：排序（Sorting）
将堆顶元素（最大值）与堆末尾元素交换，并逐步缩小堆的范围。
- 交换堆顶与末尾元素：
- 将堆顶（最大值）与当前堆的最后一个元素交换。
- 此时，最大值被放到数组末尾。
- 调整剩余堆：
- 对新的堆顶元素执行 Sift Down，重新满足堆性质。
- 堆的大小减 1（排除已排序的部分）。
- 重复直到堆为空：
- 重复交换和调整，直到所有元素有序。
3. 示例演示
假设对数组 [4, 10, 3, 5, 1] 进行升序排序（使用最大堆）。
步骤 1：建堆
初始数组：[4, 10, 3, 5, 1]
完全二叉树表示：
4
/ \
10 3
/ \
5 1- 最后一个非叶子节点是 10（索引 1）。调整 10：它比子节点 5 和 1 大，无需交换。
- 调整 4（索引 0）：4 比左子节点 10 小，交换 4 和 10。子树 [4, 5, 1] 继续调整：4 比 5 小，交换 4 和 5。最终堆：
10
/ \
5 3
/ \
4 1步骤 2：排序
- 交换堆顶 10 和末尾 1：数组变为 [1, 5, 3, 4, 10]。堆范围缩小为 [1, 5, 3, 4]。
- 调整 1：1 与 5 交换，再与 4 交换：堆变为 [5, 4, 3, 1]。
- 交换堆顶 5 和末尾 1：数组变为 [1, 4, 3, 5, 10]。堆范围缩小为 [1, 4, 3]。
- 重复上述过程，最终得到有序数组 [1, 3, 4, 5, 10]。
4. 时间复杂度
- 建堆：O(n)。
- 排序：每次 Sift Down 是 O(log n)，共 n-1 次，因此为 O(n log n)。
- 总时间复杂度：O(n log n)。
- 空间复杂度：O(1)（原地排序）。
5. 代码实现（Python）
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[0], arr[i] = arr[i], arr[0] # 交换堆顶和末尾
heapify(arr, i, 0) # 调整剩余堆
# 测试
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("排序后数组:", arr) # 输出: [1, 3, 4, 5, 10]堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的比较排序算法。它的执行过程可以分为两个主要阶段：建堆（Heapify）和排序（Sorting）。下面详细解释堆排序的执行过程。
1. 堆的基本概念
- 二叉堆：一种完全二叉树，满足堆性质：最大堆：每个父节点的值大于或等于其子节点的值。最小堆：每个父节点的值小于或等于其子节点的值。
- 堆的存储：通常用数组表示，对于节点 i：左子节点：2i + 1右子节点：2i + 2父节点：(i - 1)/2
2. 堆排序的步骤
阶段一：建堆（Heapify）
将无序数组构建成一个堆（通常为最大堆）。
- 从最后一个非叶子节点开始调整：
- 最后一个非叶子节点的索引为 n/2 - 1（n 是数组长度）。
- 从该节点开始，依次向前调整每个子树，使其满足堆性质。
- 调整方法（Sift Down）：
- 比较当前节点与其左右子节点的值。
- 如果当前节点小于某个子节点（最大堆），则交换它们。
- 递归调整被交换的子节点，直到当前节点满足堆性质。
阶段二：排序（Sorting）
将堆顶元素（最大值）与堆末尾元素交换，并逐步缩小堆的范围。
- 交换堆顶与末尾元素：
- 将堆顶（最大值）与当前堆的最后一个元素交换。
- 此时，最大值被放到数组末尾。
- 调整剩余堆：
- 对新的堆顶元素执行 Sift Down，重新满足堆性质。
- 堆的大小减 1（排除已排序的部分）。
- 重复直到堆为空：
- 重复交换和调整，直到所有元素有序。
3. 示例演示
假设对数组 [4, 10, 3, 5, 1] 进行升序排序（使用最大堆）。
步骤 1：建堆
初始数组：[4, 10, 3, 5, 1]
完全二叉树表示：
复制4 / \ 10 3 / \ 5 1
- 最后一个非叶子节点是 10（索引 1）。调整 10：它比子节点 5 和 1 大，无需交换。
- 调整 4（索引 0）：4 比左子节点 10 小，交换 4 和 10。子树 [4, 5, 1] 继续调整：4 比 5 小，交换 4 和 5。最终堆：
复制10 / \ 5 3 / \ 4 1
步骤 2：排序
- 交换堆顶 10 和末尾 1：数组变为 [1, 5, 3, 4, 10]。堆范围缩小为 [1, 5, 3, 4]。
- 调整 1：1 与 5 交换，再与 4 交换：堆变为 [5, 4, 3, 1]。
- 交换堆顶 5 和末尾 1：数组变为 [1, 4, 3, 5, 10]。堆范围缩小为 [1, 4, 3]。
- 重复上述过程，最终得到有序数组 [1, 3, 4, 5, 10]。
4. 时间复杂度
- 建堆：O(n)。
- 排序：每次 Sift Down 是 O(log n)，共 n-1 次，因此为 O(n log n)。
- 总时间复杂度：O(n log n)。
- 空间复杂度：O(1)（原地排序）。
5. 代码实现（Python）
python复制
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[0], arr[i] = arr[i], arr[0] # 交换堆顶和末尾
heapify(arr, i, 0) # 调整剩余堆
# 测试
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("排序后数组:", arr) # 输出: [1, 3, 4, 5, 10]6. 关键点总结
- 建堆：从下往上调整，确保每个子树满足堆性质。
- 排序：每次将堆顶（最大值）交换到末尾，并调整剩余堆。
- 稳定性：堆排序是不稳定的排序算法（相同元素的相对位置可能改变）。
- 适用场景：适合数据量大的情况，但不如快速排序和归并排序常用（因缓存不友好）。