堆排序

概述

堆排序（Heapsort） 是一种基于 二叉堆 数据结构的原地（in-place）比较排序算法，由 Williams 于 1964 年提出，最坏情况时间复杂度为 $O(n\lg n)$。

定义

堆排序

堆排序算法分为两个阶段：

1. 建堆阶段：调用 BUILD-MAX-HEAP 将输入数组 $A[\mathrm{1..}n]$ 转化为最大堆，耗时 $O(n)$。
2. 排序阶段：重复执行 $n-1$ 次以下操作：
   • 交换 $A[1]$（当前最大值）与 $A[\text{heap-size}]$（堆末尾元素）。
   • 将 $\text{heap-size}$ 减 1。
   • 对新的 $A[1]$ 调用 MAX-HEAPIFY 恢复堆性质，耗时 $O(\lg n)$。

排序阶段总耗时 $O(n\lg n)$，因此堆排序的总时间复杂度为 $O(n\lg n)$。

核心性质

时间复杂度

• 最坏情况：$O(n\lg n)$
• 最好情况：$\Omega (n\lg n)$（即使输入已有序，仍需建堆和排序）
• 平均情况：$\Theta (n\lg n)$

空间复杂度

• 原地排序，仅需 $O(1)$ 额外空间。

不稳定性

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

与归并排序的对比

性质	堆排序	归并排序
最坏时间	$O(n\lg n)$	$O(n\lg n)$
空间	$O(1)$	$O(n)$
稳定性	不稳定	稳定
缓存性能	较差（数组跳跃访问）	较好（顺序访问）

章节扩展

第6章：堆排序

堆排序是第6章的核心算法，完整展示了二叉堆数据结构在排序中的应用。

第8章：排序下界

堆排序达到了比较排序的下界 $O(n\lg n)$，是最优的比较排序算法之一。

第21章：最小生成树

Prim算法的优先队列通常用二叉堆实现，核心操作是 EXTRACT-MIN（O(lg V)）和 DECREASE-KEY（O(lg V)）。堆排序中建立的 MAX-HEAP 与 Prim 中的 MIN-HEAP 结构对称。

第22章：单源最短路径

Dijkstra算法的优先队列同样基于堆。EXTRACT-MIN 和 DECREASE-KEY 是两个核心操作。使用二叉堆时总时间 O((V+E) lg V)，斐波那契堆可将 DECREASE-KEY 优化至 O(1) 均摊。

参见

• 归并排序
• 二叉堆
• BUILD-MAX-HEAP
• MAX-HEAPIFY