第06章 堆排序 — 章节汇总

章节概览

本章是 Part II 排序与序统计的开篇，引入了堆（Heap）这一重要数据结构，并基于堆设计了堆排序（Heapsort）算法和优先队列（Priority Queue）。堆排序兼具归并排序的 $O(n\lg n)$ 渐近最优性和插入排序的原地排序特性，是比较排序中理论与实践并重的经典算法。本章还系统介绍了堆数据结构的维护、构建方法，以及基于堆的高效优先队列实现，这些内容在后续章节（如 Dijkstra 最短路径、最小生成树等）中将反复出现。

---

6.1~6.2 堆数据结构与维护

小节	核心主题	关键结论
6.1 堆	二叉堆的定义与数组表示	近似完全二叉树；PARENT/LEFT/RIGHT；高度 $\lfloor \lg n\rfloor$
6.2 维护堆性质	MAX-HEAPIFY 过程	”下沉”操作；$T(n)\le T(2n/3)+\Theta (1)=O(\lg n)$

核心思路：二叉堆是一种用数组表示的近似完全二叉树，满足最大堆性质（父节点 $\ge$ 子节点）或最小堆性质（父节点 $\le$ 子节点）。通过 PARENT、LEFT、RIGHT 三个简单算术过程，可以在 $O(1)$ 时间内定位任意节点的父节点和子节点。MAX-HEAPIFY 是堆操作的核心原语：当某个节点可能违反最大堆性质时，通过将其与较大的子节点交换并递归修复，在 $O(\lg n)$ 时间内恢复堆性质。

---

6.3~6.4 建堆与堆排序

小节	核心主题	关键结论
6.3 建堆	BUILD-MAX-HEAP 过程	自底向上调用 MAX-HEAPIFY；时间 $O(n)$（非 $O(n\lg n)$）
6.4 堆排序算法	HEAPSORT 过程	原地排序；$O(n\lg n)$；不稳定排序

核心思路：BUILD-MAX-HEAP 通过自底向上地对每个非叶节点调用 MAX-HEAPIFY，将无序数组转化为最大堆。关键洞察在于建堆的精确上界是 $O(n)$ 而非直觉上的 $O(n\lg n)$——因为大部分节点位于堆的底层，MAX-HEAPIFY 在底层节点上的操作代价很小。HEAPSORT 在建堆后，反复将堆顶最大元素与末尾交换并缩小堆规模，通过 $n-1$ 次 MAX-HEAPIFY 实现原地排序，总时间 $O(n\lg n)$。

---

6.5 优先队列

小节	核心主题	关键结论
6.5 优先队列	基于堆的优先队列实现	INSERT $O(\lg n)$；EXTRACT-MAX $O(\lg n)$；MAXIMUM $O(1)$；INCREASE-KEY $O(\lg n)$

核心思路：优先队列是一种维护带键值元素集合的数据结构，支持插入、取最大/最小、删除极值、修改键值等操作。基于最大堆实现的优先队列，所有操作均在 $O(\lg n)$ 或 $O(1)$ 时间内完成，远优于基于有序数组或无序数组的实现。优先队列在操作系统调度、图算法（Dijkstra、Prim）、事件驱动模拟等领域有广泛应用。

---

本章核心知识点

关键定义

概念	定义	出处
二叉堆(最大堆)	近似完全二叉树，满足 $A[\text{PARENT}(i)]\ge A[i]$	6.1 堆
堆高度	堆中根节点到叶节点的最长简单路径上的边数，$\lfloor \lg n\rfloor$	6.1 堆
优先队列	维护带键值元素集合 $S$，支持 INSERT/MAXIMUM/EXTRACT-MAX/INCREASE-KEY	6.5 优先队列

关键过程与复杂度

过程	功能	时间复杂度
MAX-HEAPIFY	维护以 $i$ 为根的子树的最大堆性质	$O(\lg n)$
BUILD-MAX-HEAP	将数组转化为最大堆	$O(n)$
HEAPSORT	原地排序	$O(n\lg n)$
INSERT	向优先队列插入元素	$O(\lg n)$
EXTRACT-MAX	删除并返回最大元素	$O(\lg n)$
INCREASE-KEY	增大指定元素的键值	$O(\lg n)$
MAXIMUM	返回最大元素	$O(1)$

核心分析工具

堆操作分析链：
  数组表示 → PARENT/LEFT/RIGHT(O(1)) → MAX-HEAPIFY(O(lg n))
    → BUILD-MAX-HEAP(O(n)) → HEAPSORT(O(n lg n))
    → 优先队列操作(O(lg n) 或 O(1))

---

与前序章节的知识关联

前序章节	关联方式
第2章 入门	循环不变式用于证明 BUILD-MAX-HEAP 和 HEAPSORT 的正确性；插入排序/归并排序作为对比
第3章 运行时间刻画	渐近记号用于表达所有堆操作的复杂度
第4章 分治策略	主定理用于分析 MAX-HEAPIFY 的递归关系式 $T(n)\le T(2n/3)+\Theta (1)$
第5章 概率分析	随机化堆（Randomized Heapsort）的期望分析

---

学习路线

第6章学习路径：
  6.1 堆（数据结构定义，建立直觉）
    → 6.2 维护堆性质（核心原语 MAX-HEAPIFY）
      → 6.3 建堆（自底向上构建）
        → 6.4 堆排序算法（排序应用）
          → 6.5 优先队列（扩展应用）

学习建议

本章是数据结构驱动的算法设计的典型范例。建议按 6.1 → 6.2 → 6.3 → 6.4 → 6.5 的顺序学习。6.2 节的 MAX-HEAPIFY 是所有堆操作的基础，务必彻底理解其”下沉”机制和 $O(\lg n)$ 的分析。6.3 节的 $O(n)$ 建堆上界是一个容易出错的考点，需要理解为什么直觉上的 $O(n\lg n)$ 不是紧上界。6.5 节的优先队列将在后续图算法中反复出现，建议重点掌握。

堆排序