一、什么是堆排序？¶
堆排序是一种利用“堆”这种数据结构进行排序的算法。堆是一种特殊的完全二叉树，我们可以把它想象成一棵“金字塔”——大顶堆的金字塔尖最大，下面的节点都比它小；小顶堆则相反，尖最小，下面的节点都比它大。堆排序通常使用大顶堆来排序，每次取出堆顶的最大值，逐步完成整个数组的排序。
二、堆的基本概念¶
-
堆的定义：堆是一棵完全二叉树（每一层都从左到右填满，最后一层可能不填满），且满足以下性质：
- 大顶堆：每个父节点的值都大于或等于子节点的值（根节点是最大值）。
- 小顶堆：每个父节点的值都小于或等于子节点的值（根节点是最小值）。 -
数组表示堆：为了方便操作，堆通常用数组表示。对于数组中索引为
i的节点：
- 左子节点索引：2i + 1
- 右子节点索引：2i + 2
- 父节点索引：(i - 1) // 2（整数除法）
三、堆排序的核心思想¶
堆排序的核心是“先建堆，再排序”：
1. 构建堆：将待排序数组转换为大顶堆（或小顶堆），此时堆顶元素是数组中的最大值（或最小值）。
2. 取出堆顶并调整：将堆顶元素（最大值）与数组末尾元素交换，此时末尾元素已排好序；然后将剩余元素重新调整为堆，重复此过程，直到所有元素排序完成。
四、堆排序的实现步骤¶
以大顶堆为例，具体步骤如下：
步骤1：构建大顶堆
- 从数组的最后一个非叶子节点开始，向上逐层调整，确保每个节点都满足“父节点 ≥ 子节点”的大顶堆性质。
- 关键操作：堆化（Heapify）。对于一个节点，比较它与左右子节点，将最大值交换到当前节点位置，然后递归调整子节点，直到子树也满足大顶堆性质。
步骤2：排序过程
- 交换堆顶元素（最大值）与数组末尾未排序元素，此时末尾元素已排好序。
- 堆的大小减1（排除已排序的末尾元素），重新对剩余元素进行堆化，重复上述交换和堆化，直到堆中只剩一个元素。
五、堆排序的代码示例（Python）¶
为了更直观，用Python实现堆排序的核心逻辑：
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[i], arr[0] = arr[0], arr[i] # 交换堆顶（最大值）与末尾元素
heapify(arr, i, 0) # 调整剩余元素的堆结构
return arr
def heapify(arr, n, i):
# 堆化函数：以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) # 递归调整子树
六、时间复杂度详解¶
堆排序的时间复杂度可以从两个部分分析：
-
构建堆的时间复杂度：
构建堆时，需要从最后一个非叶子节点开始向上堆化，共需n/2次堆化操作。每次堆化的时间复杂度是O(log k)（k为当前堆的高度），但整体计算下来，构建堆的总时间复杂度是 O(n)（可理解为所有节点的堆化操作总和接近n）。 -
排序过程的时间复杂度：
排序过程需要执行n-1次堆化（每次取出堆顶后调整剩余元素），每次堆化的时间复杂度是O(log n)（堆的高度为log n）。因此，排序过程总时间复杂度为O(n log n)。
总结：堆排序的总时间复杂度为 O(n log n)（最好、最坏、平均情况均为 O(n log n)），空间复杂度为 O(1)（原地排序，仅需常数额外空间）。
七、堆排序的特点¶
- 稳定性：不稳定（例如数组 [3, 2, 2] 排序后可能变成 [3, 2, 2]，但原数组中两个2的相对顺序可能被改变）。
- 适用场景：适合大规模数据排序，尤其是内存有限时（原地排序）。
八、总结¶
堆排序通过“构建堆→取出堆顶→调整堆”的循环过程，将无序数组转化为有序数组。其核心优势是时间复杂度稳定在 O(n log n)，适合处理大数据量。虽然实现过程稍复杂，但逻辑清晰，是排序算法中的经典选择。