第17课：堆排序 (Heap Sort)

所属模块： 排序算法 难度： Intermediate 标签： heap-sort, heap, sift-down 上一课： 第16课 - 快速排序 下一课： 第18课 - 计数排序

1. 学习目标

完成本课学习后，你将能够：

理解二叉堆（完全二叉树）作为数据结构的概念，以及它在数组中的存储方式。
掌握“下滤”操作如何维持堆的性质。
描述堆排序算法两个核心阶段（建堆、排序）的工作原理。
实现一个时间复杂度为 O(n log n) 的原地堆排序算法。
分析堆排序在时间、空间复杂度和稳定性方面的特点。

2. 核心概念

什么是堆？

想象你有一组数据，想快速找到其中的最大值。一个高效的方法是把它们组织成一棵完全二叉树，并确保任何一个父节点的值都大于或等于其子节点的值。这种结构就叫做最大堆。反之，如果父节点的值总是小于或等于子节点，就是最小堆。

堆的一个巨大优势是，虽然它是一棵树，但我们不需要使用指针来链接节点，而是可以简单地用一个数组来存储。这种存储方式非常紧凑和高效。

对于数组索引 i（从0开始）的节点：
- 它的左孩子索引是 2*i + 1
- 它的右孩子索引是 2*i + 2
- 它的父节点索引是 (i-1) // 2 (整数除法)

堆排序如何工作？

堆排序利用堆的特性来排序，过程分为两大步：

建堆 (Heapify)：把一个无序的数组转换成一个最大堆。我们从最后一个非叶子节点开始，向前逐个节点执行“下滤”操作，确保以该节点为根的子树满足堆的性质。当根节点也被处理后，整个数组就变成了一个最大堆。此时，数组的第一个元素（根节点）就是整个数组的最大值。
排序：
- 将堆顶（最大值）与当前堆的最后一个元素交换。这样，最大值就被放到了数组末尾，属于已排序的部分。
- 堆的大小减1（排除已排好序的末尾元素）。
- 此时，新的堆顶可能不满足堆的性质，因此需要对根节点执行一次“下滤”操作，重新调整剩余元素，使其再次成为一个最大堆。
- 重复上述步骤，直到堆中只剩下一个元素。此时，整个数组就有序了。

关键操作：下滤 (Sift-Down)

“下滤”是维护堆性质的核心。当一个节点（比如根节点）的值变小，可能比它的孩子小时，我们就需要把它“下沉”到合适的位置。过程如下：

比较当前节点与其左右孩子。
找出三者中的最大值。
如果最大值不是当前节点，就将当前节点与最大值的孩子交换位置。
由于发生了交换，被交换下去的孩子节点位置可能又不满足堆性质了，因此需要以该孩子为新的当前节点，重复上述步骤，直到它下沉到叶子节点或比所有孩子都大为止。

3. 代码示例

下面是一个完整的、可运行的Python实现，包含详细注释。

def heap_sort(arr):
    """
    使用最大堆对数组进行原地排序。
    :param arr: 待排序的列表
    :return: 排序后的列表（原地操作，也返回引用）
    """
    n = len(arr)

    # 1. 建堆 (Heapify) - 从最后一个非叶子节点开始
    # 最后一个非叶子节点的索引是 (n // 2 - 1)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # 2. 排序 - 逐个提取最大值到末尾
    for i in range(n - 1, 0, -1):
        # 将当前最大值（堆顶）交换到数组末尾
        arr[0], arr[i] = arr[i], arr[0]
        # 在缩小的堆（大小为 i）上，对新的堆顶进行下滤，恢复堆性质
        sift_down(arr, i, 0)

    return arr

def sift_down(arr, heap_size, root_index):
    """
    对以 root_index 为根的子树进行下滤操作，使其满足最大堆性质。
    :param arr: 数组
    :param heap_size: 当前堆的有效大小（用于忽略末尾已排序元素）
    :param root_index: 需要下滤的节点的索引
    """
    largest = root_index  # 初始化最大值为根节点
    left_child = 2 * root_index + 1
    right_child = 2 * root_index + 2

    # 如果左孩子存在且比当前最大值大，则更新最大值
    if left_child < heap_size and arr[left_child] > arr[largest]:
        largest = left_child

    # 如果右孩子存在且比当前最大值大，则更新最大值
    if right_child < heap_size and arr[right_child] > arr[largest]:
        largest = right_child

    # 如果最大值不是根节点，则需要交换并继续下滤
    if largest != root_index:
        arr[root_index], arr[largest] = arr[largest], arr[root_index]
        # 递归地对被交换下去的子节点进行下滤
        sift_down(arr, heap_size, largest)

# 测试代码
if __name__ == "__main__":
    my_list = [12, 11, 13, 5, 6, 7]
    print("原始数组:", my_list)
    sorted_list = heap_sort(my_list)
    print("排序后数组:", sorted_list)

    # 另一个测试
    my_list2 = [4, 10, 3, 5, 1]
    print("原始数组:", my_list2)
    sorted_list2 = heap_sort(my_list2)
    print("排序后数组:", sorted_list2)

预期输出:

原始数组: [12, 11, 13, 5, 6, 7]
排序后数组: [5, 6, 7, 11, 12, 13]
原始数组: [4, 10, 3, 5, 1]
排序后数组: [1, 3, 4, 5, 10]

4. 实践练习

基础验证：修改上面的代码，在 heap_sort 函数的“建堆”和每次“排序”循环后，打印出当前的数组状态。观察数组是如何从无序变为有序的，并理解每一步堆的变化。
实现最小堆排序：基于提供的最大堆排序代码，修改 sift_down 函数的比较逻辑，实现一个最小堆排序，使得数组按降序排列。测试用例：输入 [3, 1, 4, 1, 5, 9]，预期输出为 [9, 5, 4, 3, 1, 1]。
思考题：在建堆阶段，我们从索引 n//2 - 1 开始向前遍历。为什么是从这个索引开始，而不是从 0 或 n-1 开始？（提示：叶子节点没有孩子，无法执行有意义的下滤操作）。

5. 常见错误

索引混淆：堆排序中数组索引通常从0开始，但很多教材示意图从1开始。这会导致计算左右孩子和父节点的公式不同（例如，左孩子是 2*i 还是 2*i+1）。请务必统一并仔细检查你的公式。
建堆起始点错误：认为建堆需要从第一个元素开始。实际上，所有叶子节点（索引从 n//2 到 n-1）本身就是一个大小为1的堆，无需调整。建堆应从最后一个非叶子节点（n//2 - 1）开始，自底向上进行。
heap_size 使用错误：在 sift_down 函数中，必须使用传入的 heap_size 参数来判断孩子是否越界，而不是 len(arr)。因为在排序阶段，数组末尾的部分元素已经不属于堆了。
忘记递归下滤：在 sift_down 中，交换节点后，必须对新的子树根节点（即被交换下去的孩子）继续进行下滤，直到条件不满足。否则，可能只修复了一层，下面的子树仍然是无序的。

6. 小结

堆是一种基于完全二叉树的特殊数据结构，可以高效地用数组表示。最大堆的堆顶始终是最大值。
堆排序通过建堆和逐步提取最大值两个阶段完成排序，是一种原地的排序算法。
下滤操作是维护和调整堆结构的核心，它通过不断将节点与其较大的子节点交换来保证堆的性质。
时间复杂度：建堆 O(n)，排序阶段 n-1 次下滤操作，每次 O(log n)，因此总时间复杂度为 O(n log n)。
空间复杂度：O(1)，因为是原地排序，只用了常数级别的额外空间。
稳定性：不稳定。在交换堆顶和末尾元素时，可能会改变相等元素的相对顺序。
与快速排序相比，堆排序在最坏情况下也能保持 O(n log n) 的时间复杂度，但通常其常数因子较大，在实践中平均性能略逊于优化良好的快速排序。

练习编辑器

rust