堆排序原理与Python实现详解

老师好，我是刘同学

428人浏览 · 2026-03-15 11:13:36

老师好，我是刘同学 · 2026-03-15 11:13:36 发布

堆排序算法详解：原理、Python实现与动图演示

堆排序是一种基于完全二叉树结构的高效排序算法，它通过构建大顶堆或小顶堆来实现排序。下面我将从算法原理、时间复杂度、Python实现和可视化演示等方面进行全面讲解。

1. 堆排序算法原理

1.1 基本概念

堆是一种特殊的完全二叉树，分为两种类型：

大顶堆：每个节点的值都大于或等于其子节点的值
小顶堆：每个节点的值都小于或等于其子节点的值

在堆排序中，我们通常使用大顶堆来进行升序排序，因为大顶堆的根节点总是最大值。

1.2 算法步骤

堆排序主要分为两个阶段：

阶段	描述	目的
构建堆	将无序数组构建成大顶堆	建立堆结构
排序	反复取出堆顶元素并调整堆	完成排序

具体的执行流程如下：

构建大顶堆：从最后一个非叶子节点开始，自底向上调整堆
堆排序：
- 将堆顶元素（最大值）与末尾元素交换
- 减少堆的大小，重新调整堆
- 重复上述过程直到堆大小为1

1.3 关键操作：堆调整

堆调整（Heapify）是堆排序的核心操作，它确保父节点的值大于子节点的值：

def heapify(arr, n, i):
    """
    堆调整函数
    :param arr: 待调整的数组
    :param n: 堆的大小
    :param 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)  # 递归调整受影响的子树

2. 完整的Python实现

下面是堆排序的完整Python代码实现：

def heap_sort(arr):
    """
    堆排序主函数
    :param arr: 待排序的数组
    :return: 排序后的数组
    """
    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[0], arr[i] = arr[i], arr[0]
        # 调整剩余元素使其满足堆性质
        heapify(arr, i, 0)
    
    return arr

# 辅助函数：堆调整
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)

# 测试示例
if __name__ == "__main__":
    # 测试数据
    test_array = [12, 11, 13, 5, 6, 7]
    print("原始数组:", test_array)
    
    # 执行堆排序
    sorted_array = heap_sort(test_array.copy())
    print("排序后数组:", sorted_array)
    
    # 更多测试用例
    test_cases = [
        [4, 10, 3, 5, 1],
        [64, 34, 25, 12, 22, 11, 90],
        [1],
        []
    ]
    
    for i, case in enumerate(test_cases):
        print(f"测试用例 {i+1}: {case} -> {heap_sort(case.copy())}")

3. 算法执行过程详解

3.1 构建堆的过程

以数组 [12, 11, 13, 5, 6, 7] 为例，构建大顶堆的过程：

初始数组对应的完全二叉树：

从最后一个非叶子节点开始调整：
- 节点11（索引1）：比较11、5、6，无需调整
- 节点12（索引0）：比较12、11、13，13最大，交换12和13

调整后的堆：

3.2 排序过程演示

排序阶段的详细步骤：

步骤	操作	当前堆	已排序部分
1	交换堆顶13和末尾7	[7, 11, 12, 5, 6, 13]	[13]
2	调整堆	[12, 11, 7, 5, 6, 13]	[13]
3	交换堆顶12和末尾6	[6, 11, 7, 5, 12, 13]	[12, 13]
4	调整堆	[11, 6, 7, 5, 12, 13]	[12, 13]
5	继续执行直到完成	...	...

4. 算法特性分析

4.1 时间复杂度

堆排序的时间复杂度分析如下：

情况	时间复杂度	说明
最好情况	O(n log n)	已经是有序堆的情况
平均情况	O(n log n)	随机数据
最坏情况	O(n log n)	逆序数据

4.2 空间复杂度

堆排序是原地排序算法，空间复杂度为 O(1)，因为它只需要常数级别的额外空间。

4.3 稳定性

堆排序是不稳定的排序算法。在交换堆顶元素和末尾元素时，可能会改变相同元素的相对顺序。

5. 动图演示原理

虽然无法直接嵌入动图，但我可以描述堆排序的动图演示过程：

动图演示的关键帧：

初始状态：显示无序数组对应的完全二叉树
构建堆阶段：
- 高亮显示当前调整的非叶子节点
- 显示节点比较和交换过程
- 展示堆结构的逐步建立
排序阶段：
- 堆顶元素（红色）与末尾元素（绿色）交换
- 交换后堆顶元素移动到已排序区域
- 重新调整剩余堆，确保堆性质
- 重复此过程直到完全排序

视觉特征：

当前操作的节点用不同颜色高亮
交换过程用动画箭头表示
已排序部分与未排序部分用不同背景色区分

6. 应用场景与优缺点

6.1 适用场景

场景	理由
需要O(n log n)时间复杂度	堆排序在最坏情况下也能保证O(n log n)
内存受限环境	原地排序，空间复杂度O(1)
实时系统	时间复杂度稳定，没有最坏情况退化

6.2 优缺点对比

优点	缺点
时间复杂度稳定为O(n log n)	不稳定排序
原地排序，空间效率高	常数因子较大，实际性能不如快速排序
适用于大数据集	缓存不友好

7. 与其他排序算法对比

堆排序在经典排序算法中的地位：

算法	平均时间复杂度	空间复杂度	稳定性	特点
堆排序	O(n log n)	O(1)	不稳定	原地排序，最坏情况好
快速排序	O(n log n)	O(log n)	不稳定	平均情况最快
归并排序	O(n log n)	O(n)	稳定	稳定排序，需要额外空间
插入排序	O(n²)	O(1)	稳定	小数据高效