堆排序 (Heap Sort)基于堆结构的选择排序摘要快速排序最坏退化为 O(n²)归并排序需要 O(n) 额外空间。堆排序利用完全二叉树的堆结构在 O(1) 空间内实现始终 O(n log n) 的排序。本文从堆结构出发图解建堆与排序两个阶段剖析下沉操作的核心逻辑给出支持升序/降序的 Python 完整实现对比堆排序与前几种排序的差异并分析优先队列、Top-K 等工程应用场景。本文属于专栏《算法》系列 1 第 5 篇 | 上一篇归并排序 (Quick Sort)| 下一篇1-6-插入排序-InsertionSort文章目录堆排序 (Heap Sort)基于堆结构的选择排序一、问题引入二、算法原理图解堆结构基础核心思想阶段一建堆过程阶段二排序过程下沉操作图解与前几种排序的对比三、代码实现完整实现运行验证四、复杂度分析时间复杂度空间复杂度稳定性五、横向对比三种 O(n log n) 排序的权衡六、工程实战堆结构的核心应用优先队列Top-K 问题堆排序的杀手级应用为什么标准库不直接用堆排序七、常见误区与面试题高频面试题常见实现错误八、总结一、问题引入前面几种排序各有遗憾冒泡/插入排序O(n²)大规模数据不可用快速排序平均 O(n log n)但最坏退化为 O(n²)归并排序始终 O(n log n)但需要 O(n) 额外空间能否做到最坏 O(n log n) 原地排序 O(1) 空间考虑选择排序的核心思路每轮从未排序部分选出极值放到正确位置。朴素选择排序每次线性扫描找极值总复杂度 O(n²)。如果用一种高效的数据结构来维护极值呢堆正是这样的结构——一种完全二叉树父节点始终大于最大堆或小于最小堆子节点堆顶即极值获取极值 O(1)调整堆 O(log n)。堆排序的回答先建堆再反复取堆顶极值放到末尾缩小堆范围后重新调整。问题定义输入含 n 个元素的可比较数组arr输出按升序或降序排列的数组核心操作建堆 → 交换堆顶到末尾 → 下沉调整 → 重复二、算法原理图解堆结构基础堆是用数组表示的完全二叉树节点间的索引关系数组索引: 0 1 2 3 4 5 6 数组值: [7, 5, 6, 1, 3, 2, 4] 对应的完全二叉树 7(0) / \ 5(1) 6(2) / \ / \ 1(3) 3(4) 2(5) 4(6) 最大堆性质每个父节点 ≥ 子节点 索引关系0 为根 父节点索引: (i - 1) // 2 左子节点索引: 2 * i 1 右子节点索引: 2 * i 2核心思想堆排序分两个阶段建堆 (Build Heap)将无序数组调整为最大堆升序或最小堆降序排序 (Sort)反复将堆顶极值与末尾交换缩小堆范围对堆顶下沉调整阶段一建堆过程从最后一个非叶子节点索引n//2 - 1开始自底向上对每个节点执行下沉操作原始数组: [4, 10, 3, 5, 1] 对应树: 4(0) / \ 10(1) 3(2) / \ 5(3) 1(4) 最后一个非叶子节点: n//2 - 1 5//2 - 1 1 步骤1: 下沉节点1 (值10) 子节点: left3(值5), right4(值1) 10 5 且 10 1已满足最大堆无需交换 堆: [4, 10, 3, 5, 1] 步骤2: 下沉节点0 (值4) 子节点: left1(值10), right2(值3) 10 最大交换 4 和 10 堆: [10, 4, 3, 5, 1] 继续下沉节点1 (值4): 子节点: left3(值5), right4(值1) 5 最大交换 4 和 5 堆: [10, 5, 3, 4, 1] 节点3 是叶子结束 建堆完成: [10, 5, 3, 4, 1] 对应树: 10 / \ 5 3 / \ 4 1阶段二排序过程建堆后: [10, 5, 3, 4, 1] 堆范围 [0~4] 第1轮: 交换堆顶10和末尾1 → [1, 5, 3, 4, |10] 下沉堆顶1 → [5, 4, 3, 1, |10] 第2轮: 交换堆顶5和末尾1 → [1, 4, 3, |5, 10] 下沉堆顶1 → [4, 1, 3, |5, 10] 第3轮: 交换堆顶4和末尾3 → [3, 1, |4, 5, 10] 下沉堆顶3 → [3, 1, |4, 5, 10] (已满足堆性质) 第4轮: 交换堆顶3和末尾1 → [1, |3, 4, 5, 10] 下沉堆顶1 → [1, |3, 4, 5, 10] (单元素结束) 最终结果: [1, 3, 4, 5, 10]竖线|右侧为已排序部分每轮堆顶极值归位堆范围左移一位。下沉操作图解下沉 (_sift_down) 是堆排序的核心——将一个可能违反堆性质的节点向下调整下沉节点 index值为4最大堆 4(index) 10 / \ → / \ 10(L) 3(R) 4 3 / \ / \ 5 1 5 1 步骤 1. 比较节点4与子节点10、3找最大值10 2. 10 4交换4和10 3. 继续下沉4现在在原10的位置 4. 比较节点4与子节点5、1找最大值5 5. 5 4交换4和5 6. 节点4成为叶子结束与前几种排序的对比维度快速排序归并排序堆排序核心策略分区 递归拆分 合并建堆 选择最坏时间O(n²)O(n log n)O(n log n)空间O(log n)O(n)O(1)稳定性不稳定稳定不稳定缓存友好是一般否跳跃访问三、代码实现完整代码通过网盘分享的文件算法链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwdyyqf 提取码: yyqf–来自百度网盘超级会员v4的分享完整实现defheap_sort(arr,ascendingTrue): 堆排序利用堆结构进行选择排序。先构建堆再反复取堆顶极值放到末尾。 时间复杂度O(n log n)始终稳定 | 空间复杂度O(1) | 不稳定排序 参数: arr: 待排序列表 ascending: 排序方向True升序默认False降序 返回: 排序后的列表原地排序 nlen(arr)ifn1:returnarr# 阶段一建堆。从最后一个非叶子节点开始自底向上堆化# 升序用最大堆堆顶最大值往后放降序用最小堆foriinrange(n//2-1,-1,-1):_sift_down(arr,n,i,ascending)# 阶段二排序。每次将堆顶极值与当前末尾交换缩小堆范围后重新堆化forendinrange(n-1,0,-1):arr[0],arr[end]arr[end],arr[0]# 堆顶极值归位到末尾_sift_down(arr,end,0,ascending)# 对剩余元素重新堆化returnarrdef_sift_down(arr,heap_size,index,ascending): 下沉操作将 index 位置的元素向下调整使其满足堆性质。 升序最大堆父节点必须大于子节点大的子节点上浮 降序最小堆父节点必须小于子节点小的子节点上浮 参数: arr: 数组 heap_size: 当前堆的有效大小 index: 需要下沉的节点索引 ascending: True最大堆False最小堆 whileTrue:left2*index1# 左子节点索引right2*index2# 右子节点索引targetindex# 记录需要交换的目标位置# 升序最大堆找三个节点中的最大值# 降序最小堆找三个节点中的最小值ifascending:ifleftheap_sizeandarr[left]arr[target]:targetleftifrightheap_sizeandarr[right]arr[target]:targetrightelse:ifleftheap_sizeandarr[left]arr[target]:targetleftifrightheap_sizeandarr[right]arr[target]:targetright# 如果目标就是自身说明已满足堆性质结束下沉iftargetindex:break# 交换并继续向下调整arr[index],arr[target]arr[target],arr[index]indextarget三个关键设计自底向上建堆从n//2 - 1最后一个非叶子节点开始跳过叶子节点效率高于自顶向下逐个插入target变量统一比较先找三节点中最大或最小值的位置再判断是否需要交换避免冗余交换升序用最大堆堆顶最大值交换到末尾堆范围缩小后最大值固定在右侧最终升序排列运行验证if__name____main__:data[64,34,25,12,22,11,90]print(f排序前:{data})print(f升序:{heap_sort(data[:])})print(f降序:{heap_sort(data[:],ascendingFalse)})# 边界测试print(f空列表:{heap_sort([])})print(f单元素:{heap_sort([42])})print(f已有序:{heap_sort([1,2,3,4,5])})print(f全相同:{heap_sort([7,7,7,7,7])})print(f逆序:{heap_sort([5,4,3,2,1])})输出排序前: [64, 34, 25, 12, 22, 11, 90] 升序: [11, 12, 22, 25, 34, 64, 90] 降序: [90, 64, 34, 25, 22, 12, 11] 空列表: [] 单元素: [42] 已有序: [1, 2, 3, 4, 5] 全相同: [7, 7, 7, 7, 7] 逆序: [1, 2, 3, 4, 5]四、复杂度分析时间复杂度情况复杂度说明最好O(n log n)无论数据如何分布建堆 排序流程不变平均O(n log n)同上最坏O(n log n)同上——堆排序不会退化推导过程建堆阶段 从 n//2 - 1 到 0共 n/2 次下沉操作 每次下沉最多走 log n 步但大部分节点下沉距离远小于 log n 建堆总复杂度 O(n)非 O(n log n)这是关键结论 排序阶段 n-1 次交换 下沉 每次下沉最多走 log n 步 排序总复杂度 O(n log n) 总复杂度 O(n) O(n log n) O(n log n)建堆为什么是 O(n) 而非 O(n log n)关键在于大部分节点在底层下沉距离极短。第 k 层有 2^k 个节点每个最多下沉 (log n - k) 步总下沉步数 Σ (k0 to log n) 2^k × (log n - k) 2^(log n1) - log n - 2 ≈ 2n O(n)底层的 n/2 个叶子节点完全不下沉n/4 个节点只下沉 1 步只有根节点可能下沉 log n 步。空间复杂度O(1)——堆排序在原数组上操作仅使用index、left、right、target等常数个辅助变量。这是堆排序相对归并排序的核心优势。稳定性不稳定排序。排序阶段堆顶与末尾交换是跨距离交换可能改变相等元素的相对顺序。例如[5a, 5b, 3]建堆后[5a, 5b, 3]交换堆顶 5a 和末尾 3 后变为[3, 5b, 5a]5a 和 5b 的相对顺序被改变。五、横向对比堆排序与同系列算法的对比算法平均时间最好时间最坏时间空间稳定性特点冒泡排序O(n²)O(n)O(n²)O(1)稳定最简单快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定实际最快归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定 不退化堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地 不退化插入排序O(n²)O(n)O(n²)O(1)稳定小数据最优三种 O(n log n) 排序的权衡维度快速排序归并排序堆排序最坏时间O(n²)O(n log n)O(n log n)空间O(log n)O(n)O(1)稳定性不稳定稳定不稳定缓存友好最好一般最差实际速度最快中等最慢适用场景通用内存排序需稳定/外部排序内存受限 不退化选型建议通用排序快速排序缓存友好实际最快需要稳定归并排序或 TimSort内存受限 不能退化堆排序嵌入式系统、实时系统需要动态维护极值堆结构本身优先队列六、工程实战堆结构的核心应用优先队列堆排序的副产品——堆结构——比堆排序本身更有工程价值importheapq# Python heapq 默认最小堆data[5,1,8,3,2]heapq.heapify(data)# O(n) 建堆print(heapq.heappop(data))# 1取最小值 O(log n)heapq.heappush(data,0)# 插入元素 O(log n)print(heapq.heappop(data))# 0应用场景堆的作用任务调度最大堆按优先级取出任务Dijkstra 最短路径最小堆维护当前最短距离节点Top-K 问题大小为 K 的堆O(n log K) 求前 K 大/小合并 K 个有序链表最小堆维护各链表当前最小值中位数维护最大堆左半 最小堆右半Top-K 问题堆排序的杀手级应用importheapq# 从 100 万个数据中找最大的 10 个datarange(1000000)# 方法1排序后取前10 → O(n log n)top10_sortedsorted(data,reverseTrue)[:10]# 方法2维护大小为10的最小堆 → O(n log K) O(n log 10) ≈ O(n)top10_heapheapq.nlargest(10,data)print(top10_heap)# [999999, 999998, ..., 999990]当 K 远小于 n 时堆方法比全排序快 log(n)/log(K) 倍。为什么标准库不直接用堆排序importrandomimporttime datarandom.sample(range(100000),10000)starttime.time()heap_sort(data[:])print(f堆排序:{time.time()-start:.3f}s)starttime.time()sorted(data[:])print(fTimSort:{time.time()-start:.3f}s)典型输出n10000堆排序: 0.082s TimSort: 0.001s堆排序比 TimSort 慢 80 倍原因有二缓存不友好堆操作访问2*i1、2*i2等跳跃索引CPU 缓存命中率远低于顺序扫描的快排和归并常数因子大每轮下沉需多次比较和交换实际比较次数约为归并排序的 2 倍因此堆排序在实际排序中较少使用但堆结构作为数据结构被广泛使用。七、常见误区与面试题高频面试题Q1堆排序为什么是不稳定的排序阶段将堆顶元素与末尾元素交换这是跨距离交换。例如[5a, 5b, 3]建堆后堆顶为 5a交换 5a 和 3 后 5a 移到末尾5b 留在堆中最终 5b 可能在 5a 之前相对顺序被改变。Q2建堆的时间复杂度为什么是 O(n) 而不是 O(n log n)虽然每个节点下沉最多走 log n 步但大部分节点在底层下沉距离很短。第 k 层有 2^k 个节点每个最多走 (log n - k) 步求和后总步数约为 2n即 O(n)。只有根节点可能走满 log n 步但它只有 1 个。Q3升序排序为什么用最大堆而不是最小堆升序排序需要最大值放到末尾。最大堆的堆顶就是最大值交换到末尾后末尾位置就是最终位置。如果用最小堆堆顶是最小值交换到末尾后最小值跑到了最后与升序要求矛盾。Q4堆排序和快速排序都原地且 O(n log n)为什么快排更常用快排的顺序扫描模式对 CPU 缓存友好缓存命中率高堆排序的跳跃索引访问 (2*i1,2*i2) 导致频繁缓存未命中。在同等 O(n log n) 下快排的实际常数因子远小于堆排序。常见实现错误错误说明修正建堆从根开始自顶向下建堆为 O(n log n)从n//2-1开始自底向上O(n)下沉只比较一个子节点漏掉另一个子节点可能更大左右子节点都比找最大值排序阶段堆范围不缩小end不递减死循环range(n-1, 0, -1)递减升序用最小堆最小值交换到末尾降序排列升序用最大堆降序用最小堆heap_size传错下沉时用了数组长度而非堆范围排序阶段传end而非n八、总结堆排序的核心要点两阶段设计——O(n) 建堆 O(n log n) 排序始终不退化原地排序——O(1) 空间无需额外数组适合内存受限场景下沉操作是核心——找三节点极值交换后继续下沉直到满足堆性质不稳定 缓存不友好——跨距离交换破坏稳定性跳跃索引导致缓存命中率低堆结构比堆排序更有价值——优先队列、Top-K、Dijkstra 等场景的核心数据结构堆排序在排序算法家族中独树一帜它用 O(1) 空间实现了 O(n log n) 不退化排序这是快速排序和归并排序都做不到的。但实际性能受限于缓存不友好更多作为保底方案存在。真正让堆大放异彩的是堆结构本身——优先队列是工程中最常用的数据结构之一。专栏导航算法⬅️上一篇归并排序 (Quick Sort) ➡️下一篇1-6-插入排序-InsertionSort如果这篇文章对你有帮助欢迎点赞、收藏、关注支持专栏持续更新