第 6 章堆排序 (Heapsort)

核心结论

堆 (Heap)：近似完全二叉树的数组对象；分为最大堆（父 ≥ 子）和最小堆（父 ≤ 子）。n 元素堆的高度 = Θ(lg n)。
MAX-HEAPIFY：维护最大堆性质的关键操作；让一个节点「下沉」到正确位置，O(h) = O(lg n)。
BUILD-MAX-HEAP：自底向上对每个非叶节点调用 MAX-HEAPIFY，线性时间 Θ(n) 建立最大堆。
HEAPSORT：先建最大堆，再反复「取最大 → 放末尾 → 调整」；总运行时间 O(n lg n)，原地排序。
优先级队列 (Priority Queue)：堆的另一大应用；支持 INSERT / MAXIMUM / EXTRACT-MAX / INCREASE-KEY，全部 O(lg n)。
d 叉堆 / Young Tableau：堆的推广与变种——堆的概念在第 19 章斐波那契堆、第 24 章 Dijkstra 中再次出现。

本章主旨

本章是第一个「数据结构 + 算法」联合设计的范例：堆作为数据结构，既支撑堆排序（O(n lg n) 原地排序），又支撑优先级队列（O(lg n) 操作）。关键技巧是 MAX-HEAPIFY 的「下沉」+ BUILD-MAX-HEAP 的「自底向上」，以及 HEAPSORT 的「交换 + 减堆 + 调整」三步循环。堆作为数据结构将在后续 Dijkstra（第 24 章）、Prim（第 23 章）等算法中作为优先级队列反复使用。

一、核心概念

本章围绕 6 个核心概念展开：先给出堆的数据结构与性质，再介绍维护堆性质的 MAX-HEAPIFY、自底向上建堆的 BUILD-MAX-HEAP，最后组合为 HEAPSORT，并把堆重新用于实现优先级队列。

概念	定义 + 重要性	实现提示
堆 (Heap) 数据结构	数组对象 + 完全二叉树视图；最大堆性质 = A[PARENT(i)] ≥ A[i]。	§6.1；PARENT(i) = ⌊i/2⌋，LEFT(i) = 2i，RIGHT(i) = 2i+1。
MAX-HEAPIFY	维护最大堆性质：让 A[i]「下沉」到正确位置；O(h) = O(lg n)。	§6.2；递归式 T(n) ≤ T(2n/3) + Θ(1) → 主定理情形 2 → O(lg n)。
BUILD-MAX-HEAP	自底向上对每个内部节点调用 MAX-HEAPIFY，线性时间建堆。	§6.3；从 ⌊n/2⌋ 倒数到 1；总代价 = Σ h·⌈n/2^{h+1}⌉ = O(n)。
HEAPSORT	堆排序算法：BUILD-MAX-HEAP + 反复「取最大 + 末尾交换 + 减堆 + MAX-HEAPIFY」。	§6.4；总代价 = O(n) + (n-1)·O(lg n) = O(n lg n)，原地排序。
优先级队列 (Priority Queue)	数据结构：维护带键值元素集合；支持 MAXIMUM / EXTRACT-MAX / INSERT / INCREASE-KEY。	§6.5；全部 O(lg n)，MAXIMUM 为 Θ(1)。
堆的变种	d-ary heap（d 叉堆）、Young tableau（杨氏图表）等堆的推广。	问题 6-2、6-3；d 叉堆用于降低树高，Young tableau 用于 in-place 排序。

概念

定义 + 重要性

实现提示

堆 (Heap) 数据结构

数组对象 + 完全二叉树视图；最大堆性质 = A[PARENT(i)] ≥ A[i]。

§6.1；PARENT(i) = ⌊i/2⌋，LEFT(i) = 2i，RIGHT(i) = 2i+1。

MAX-HEAPIFY

维护最大堆性质：让 A[i]「下沉」到正确位置；O(h) = O(lg n)。

§6.2；递归式 T(n) ≤ T(2n/3) + Θ(1) → 主定理情形 2 → O(lg n)。

BUILD-MAX-HEAP

自底向上对每个内部节点调用 MAX-HEAPIFY，线性时间建堆。

§6.3；从 ⌊n/2⌋ 倒数到 1；总代价 = Σ h·⌈n/2^{h+1}⌉ = O(n)。

HEAPSORT

堆排序算法：BUILD-MAX-HEAP + 反复「取最大 + 末尾交换 + 减堆 + MAX-HEAPIFY」。

§6.4；总代价 = O(n) + (n-1)·O(lg n) = O(n lg n)，原地排序。

优先级队列 (Priority Queue)

数据结构：维护带键值元素集合；支持 MAXIMUM / EXTRACT-MAX / INSERT / INCREASE-KEY。

§6.5；全部 O(lg n)，MAXIMUM 为 Θ(1)。

堆的变种

d-ary heap（d 叉堆）、Young tableau（杨氏图表）等堆的推广。

问题 6-2、6-3；d 叉堆用于降低树高，Young tableau 用于 in-place 排序。

二、详细笔记

6.1 堆数据结构 (Heap)

What：(二叉) 堆是数组对象，可视为「近似完全二叉树」：

树根 = A[1]。
给定节点 i，父 = ⌊i/2⌋，左子 = 2i，右子 = 2i+1。
数组长度 A.length 与堆大小 A.heap-size 区分——A.heap-size ≤ A.length。

两种堆：

最大堆 (Max-Heap)：除根外，每个节点 i 满足 A[PARENT(i)] ≥ A[i]；最大元素在根。
最小堆 (Min-Heap)：相反；最小元素在根。

n 元素堆的高度 = ⌊lg n⌋。

Why：堆提供「极值访问 Θ(1) + 调整 O(lg n)」——是优先级队列的核心数据结构；同时可实现 O(n lg n) 原地排序（HEAPSORT）。

How：PARENT(i) = ⌊i/2⌋，LEFT(i) = 2i，RIGHT(i) = 2i+1（§6.1）。底层用位运算：i 移一位 = 2i；i 移一位 +1 = 2i+1；i 移一位 = ⌊i/2⌋。

堆与「Java/Lisp 堆」的命名冲突——本书中「heap」专指这个数据结构，与垃圾回收无关。

When：需要快速取极值 + 动态调整的场景——优先级队列、堆排序、Top-K 维护、Dijkstra、Prim、Huffman 编码（第 16 章）。

Example：图 6.1 —— 数组 A = ⟨16, 14, 10, 8, 7, 9, 3, 2, 4, 1⟩ 是最大堆，根 = 16（最大），树高 = 3。

6.2 维护堆性质 MAX-HEAPIFY

What：MAX-HEAPIFY(A, i) 假设以 LEFT(i) 和 RIGHT(i) 为根的子树都是最大堆，但 A[i] 可能小于孩子——让 A[i]「下沉」（递归地与较大子节点交换）直到恢复最大堆性质。

Why：MAX-HEAPIFY 是所有堆操作的「基本动作」——HEAPSORT、BUILD-MAX-HEAP、HEAP-EXTRACT-MAX、HEAP-INCREASE-KEY 都依赖它。

How：MAX-HEAPIFY 伪代码（§6.2）：

\[\begin{array}{rl} 1 & l = \text{LEFT}(i) \\ 2 & r = \text{RIGHT}(i) \\ 3 & \textbf{if } l \leq A.\text{heap-size} \textbf{ and } A[l] > A[i] \\ 4 & \quad largest = l \\ 5 & \textbf{else } largest = i \\ 6 & \textbf{if } r \leq A.\text{heap-size} \textbf{ and } A[r] > A[\text{largest}] \\ 7 & \quad largest = r \\ 8 & \textbf{if } largest \neq i \\ 9 & \quad \text{exchange } A[i] \leftrightarrow A[\text{largest}] \\ 10 & \quad \text{MAX-HEAPIFY}(A, \text{largest}) \end{array}\]

运行时间分析（§6.2）：设 T(n) = 在规模为 n 的子树上运行时间。最坏情形下子树规模 ≈ 2n/3（最后半满时），得递归式：

\[T(n) \leq T(2n/3) + \Theta(1)\]

主定理情形 2 → \(T(n) = O(\lg n)\)。

When：所有违反堆性质的「下沉」操作——HEAPSORT 的调整阶段、BUILD-MAX-HEAP 的自底向上调整、HEAP-EXTRACT-MAX。

Example：图 6.2 —— MAX-HEAPIFY(A, 2) 在 A = ⟨16, 4, 10, 14, 7, 9, 3, 2, 8, 1⟩ 上逐步下沉：交换 A[2] ↔ A[4]（14），再交换 A[4] ↔ A[9]（8），最终以 2 为根的子树恢复最大堆。

6.3 自底向上建堆 BUILD-MAX-HEAP

What：把无序数组 A[1..n] 转化为最大堆。从 ⌊n/2⌋ 倒数到 1，每个节点调用 MAX-HEAPIFY。

Why：HEAPSORT 的预处理步骤；单独的 BUILD-MAX-HEAP 也用于「把数组转化为堆」的其他场景。

How：BUILD-MAX-HEAP 伪代码（§6.3）：

\[\begin{array}{rl} 1 & A.\text{heap-size} = A.\text{length} \\ 2 & \textbf{for } i = \lfloor A.\text{length}/2 \rfloor \textbf{ downTo } 1 \\ 3 & \quad \text{MAX-HEAPIFY}(A, i) \end{array}\]

循环不变量：第 i 次迭代开始时，每个节点 i+1, i+2, …, n 都是最大堆的根。

正确性：初始化（叶节点是 trivial heap）、保持（递归调用保持子树）、终止（i = 0 时整个树是堆）。

复杂度（§6.3）：n 元素堆中高度为 h 的节点数 ≤ ⌈n/2^{h+1}⌉（问题 6-3）。MAX-HEAPIFY 在高度 h 节点上花 O(h) 时间：

\[T(n) = \sum_{h=0}^{\lfloor \lg n \rfloor} \lceil n/2^{h+1} \rceil \cdot O(h) = O\left(n \sum_{h=0}^{\infty} h/2^h\right) = O(n)\]

其中 Σ h/2^h = 2（式 A.8，x = 1/2）。所以 BUILD-MAX-HEAP 是 Θ(n)，线性时间——直觉反常但正确。

When：作为 HEAPSORT 的预处理；把任意数组转化为堆结构（如「Top-K」算法先用 BUILD-MAX-HEAP 建大小 K 的堆）。

Example：图 6.3 —— BUILD-MAX-HEAP 在 A = ⟨5, 3, 17, 10, 84, 19, 6, 22, 9⟩ 上逐步建堆，最终得到最大堆。

6.4 堆排序算法 HEAPSORT

What：HEAPSORT 算法 = BUILD-MAX-HEAP + 反复「交换 A[1] ↔ A[i]，减堆，对 A[1] 调用 MAX-HEAPIFY」。

Why：HEAPSORT 结合了插入排序（原地）和归并排序（O(n lg n)）的优点——既快又省空间。

How：HEAPSORT 伪代码（§6.4）：

\[\begin{array}{rl} 1 & \text{BUILD-MAX-HEAP}(A) \\ 2 & \textbf{for } i = A.\text{length} \textbf{ downTo } 2 \\ 3 & \quad \text{exchange } A[1] \leftrightarrow A[i] \\ 4 & \quad A.\text{heap-size} = A.\text{heap-size} - 1 \\ 5 & \quad \text{MAX-HEAPIFY}(A, 1) \end{array}\]

循环不变量：每次迭代开始时，A[1..i] 是最大堆含 i 个最小元素，A[i+1..n] 是已排序的 n-i 个最大元素。

总运行时间：

\[T(n) = O(n) + \sum_{i=2}^{n} O(\lg i) = O(n \lg n)\]

BEST / WORST / AVG 都是 Θ(n lg n)（不像快速排序，最坏不恶化到 n²）。

When：需要 O(n lg n) + 原地 + 稳定最坏性能的场景；实际中常被快速排序超越（常数因子更小），但堆排序的「最坏 O(n lg n)」是优势。

Example：图 6.4 —— HEAPSORT 在 A = ⟨5, 13, 2, 25, 7, 17, 20, 8, 4⟩ 上逐步执行：(a) BUILD-MAX-HEAP 后得到最大堆；(b)–(j) 每轮取最大到末尾；(k) 最终 A 排好序。

6.5 优先级队列 (Priority Queue)

What：维护带键值元素的集合 S，支持 INSERT、MAXIMUM、EXTRACT-MAX、INCREASE-KEY（最大优先级队列）。

Why：优先级队列是 Dijkstra（最短路径，第 24 章）、Prim（最小生成树，第 23 章）、Huffman 编码（第 16 章）、事件驱动模拟等算法的核心数据结构。

How：用最大堆实现最大优先级队列（§6.5）：

HEAP-MAXIMUM(A)：返回 A[1]，Θ(1)。
HEAP-EXTRACT-MAX(A)：保存 max = A[1]，A[1] = A[heap-size]，减堆，MAX-HEAPIFY(A, 1)——O(lg n)。
HEAP-INCREASE-KEY(A, i, key)：A[i] = key，然后向上比较父节点，若更大则交换——O(lg n)。
MAX-HEAP-INSERT(A, key)：扩堆（设 key = -∞），再 HEAP-INCREASE-KEY——O(lg n)。

应用：

作业调度：每次 EXTRACT-MAX 取优先级最高的作业。
事件驱动模拟：用最小堆 + EXTRACT-MIN 取下一个事件。

When：任何「动态取极值」场景——Dijkstra/Prim 的核心；事件驱动模拟；Top-K 流式算法；A* 搜索的 open set。

Example：图 6.5 —— HEAP-INCREASE-KEY 把节点 i 的键从 10 提升到 15：与父 14 交换，与祖父 16 比较，停止——O(lg n) 路径向上。

6.6 堆的变种（d-ary heap / Young tableau）

What：

d-ary heap：非叶节点有 d 个孩子；高度 = Θ(log_d n)，EXTRACT-MAX = O(d log_d n)，INCREASE-KEY = O(log_d n)。
Young tableau（杨氏图表）：m×n 矩阵，行从左到右递增、列从上到下递增；EXTRACT-MIN/INSERT 都是 O(m+n)。

Why：调整 d 让 INSERT / DECREASE-KEY 更便宜（如 Dijkstra 用 d-ary heap 优化）；Young tableau 提供「带约束的排序」。

How（d-ary heap，问题 6-2）：

索引：PARENT(i) = ⌈i/d⌉，j-th child = (i-1)d + j + 1。
高度 = Θ(log_d n) = Θ(lg n / lg d)。
EXTRACT-MAX 需要比较 d 个孩子 → O(d log_d n)。
- INSERT / DECREASE-KEY 只走父链 → O(log_d n)。

Young tableau（问题 6-3）：EXTRACT-MIN 取出 Y[1,1]，用 Y[m,n] 填入，再「下沉」到正确位置；INSERT 类似「上浮」。两者都 O(m+n)。

When：

d-ary heap：当 INCREASE-KEY / DECREASE-KEY 比 EXTRACT-MAX 频繁时（如 Dijkstra 用 d = 4~16 优化）。
Young tableau：用于排序 n² 个数（O(n³)，问题 6-3e）；用作优先级队列的替代实现。

Example：d-ary heap 用 d = 4 时 EXTRACT-MAX 需要比较 4 个孩子，比二叉堆慢 2 倍但 INSERT 快 1 倍——Dijkstra 中净增益。

三、关键图表

核心公式对照表

名称

内容

堆索引

PARENT(i) = ⌊i/2⌋，LEFT(i) = 2i，RIGHT(i) = 2i+1

最大堆性质

A[PARENT(i)] ≥ A[i]（i ≠ root）

堆高度

n 元素堆的高度 = ⌊lg n⌋

MAX-HEAPIFY 递归式

T(n) ≤ T(2n/3) + Θ(1) → O(lg n)

BUILD-MAX-HEAP 复杂度

Σ ⌈n/2^{h+1}⌉ · O(h) = O(n)

HEAPSORT 复杂度

O(n) + (n-1)·O(lg n) = O(n lg n)

HEAP-MAXIMUM

Θ(1)

HEAP-EXTRACT-MAX

O(lg n)

HEAP-INCREASE-KEY

O(lg n)

MAX-HEAP-INSERT

O(lg n)

d-ary heap 索引

PARENT(i) = ⌈i/d⌉；j-th child = (i-1)d + j + 1

d-ary heap EXTRACT-MAX

O(d log_d n)

四、思维导图

mindmap
  root((第 6 章 堆排序))
    堆结构
      完全二叉树
      数组表示
      最大堆性质
      高度Θ(lg n)
    MAX-HEAPIFY
      下沉
      比较孩子
      O(lg n)
    BUILD-MAX-HEAP
      自底向上
      Θ(n)线性
    HEAPSORT
      建堆
      取最大
      末尾交换
      减堆
      O(n lg n)
      原地
    优先级队列
      MAXIMUMΘ(1)
      EXTRACT-MAX
      INCREASE-KEY
      INSERT
      全部O(lg n)
    变种
      d-ary堆
      YoungTableau
      斐波那契堆
    应用
      Dijkstra
      Prim
      Huffman
      事件模拟

五、重点与易错点

堆 ≠ 垃圾回收堆：本书「heap」专指数据结构；与 Java/Lisp 的 garbage-collected heap 无关。
A.length vs A.heap-size：堆排序时用 A.heap-size 标记「当前堆大小」，从而把已排序部分排除；忘记修改 heap-size 是常见 bug。
1-indexed 数组：本书堆用 A[1..n]，PARENT(i) = ⌊i/2⌋；0-indexed 时略有不同（PARENT(i) = (i-1)/2）。
BUILD-MAX-HEAP 是 Θ(n) 不是 Θ(n lg n)：直观上「n 次 MAX-HEAPIFY 每次 O(lg n) 应是 n lg n」——但大部分 MAX-HEAPIFY 在低高度节点上，总和是 O(n)。
BUILD-MAX-HEAP 倒序循环：从 ⌊n/2⌋ 倒数到 1（不是 1 到 ⌊n/2⌋）——因为 MAX-HEAPIFY 假设「子树已是堆」，必须先处理子树。
HEAPSORT 最坏 = 平均 = O(n lg n)：不像快速排序，最坏情况不恶化；这是 HEAPSORT 的优势。
HEAP-INCREASE-KEY 必须 key ≥ 当前值：违反时报告错误（不能「降级」）；类似 INSERTION-SORT 的内层循环。
MAX-HEAP-INSERT 设为 -∞ 再 INCREASE-KEY：避免 MAX-HEAPIFY 误把刚插入的元素「下沉」；用 -∞ 哨兵让它必须上浮。
堆 vs 二叉搜索树：BST 中序遍历得到有序序列；堆只能保证「极值在根」，不能保证全局有序——这是堆排序需要 MAX-HEAPIFY n-1 次的原因。
优先级队列的 MAXIMUM Θ(1) 但 EXTRACT-MAX O(lg n)：取极值快，移除极值慢——堆的核心权衡。
Young tableau 不是堆：行列双向有序；类似「二维堆」；用于排序 + 搜索 (O(m+n))。
d-ary heap 的取舍：d 大 → EXTRACT-MAX 慢（d 个孩子比较），但 DECREASE-KEY / INSERT 快（树矮）。Dijkstra 中通常 d = 4~16 最优。
HEAPSORT 的常数因子：实践中常被快速排序超过（后者常数小 ~2x）；但 HEAPSORT 的最坏 O(n lg n) 是优势。
堆是「数组实现的树」：避免指针的随机访问开销——缓存友好；链表实现的「树」在缓存性能上差。
堆是后续章节的关键数据结构：Dijkstra、Prim、Huffman、k-路归并都依赖堆；务必掌握 MAX-HEAPIFY 与 BUILD-MAX-HEAP。

第 6 章 堆排序 (Heapsort)

核心结论

一、核心概念

二、详细笔记

6.1 堆数据结构 (Heap)

6.2 维护堆性质 MAX-HEAPIFY

6.3 自底向上建堆 BUILD-MAX-HEAP

6.4 堆排序算法 HEAPSORT

6.5 优先级队列 (Priority Queue)

6.6 堆的变种（d-ary heap / Young tableau）

三、关键图表

四、思维导图

五、重点与易错点

第 6 章堆排序 (Heapsort)