[CS225] 堆: 二叉堆、优先队列与数组实现
CS225 堆：二叉堆、优先队列与数组实现
本文对应 CS225 Spring 2026 Lecture 21 的 Heaps、Lecture 22 的 Heaps Analysis，并连接配套
lab_heaps。主线是：为什么需要堆、完全二叉树如何用数组表示、heap property 如何维护、如何实现优先队列，以及这些操作的复杂度。
课程资料与学习路线
官方资料：
- 课程日程
- Heaps 幻灯片
- Heaps 课堂 handout
- Heaps Analysis 幻灯片
- Heaps Analysis 课堂 handout
- Heaps 资源
- lab_heaps
- lab_heaps handout
- lab_heaps Fall 2025 讲解录像
本文路线：
flowchart LR
A[优先级需求] --> B[Heap ADT]
B --> C[完全二叉树]
C --> D[数组下标关系]
D --> E[heap property]
E --> F[heapify up]
E --> G[heapify down]
F --> H[push]
G --> I[pop]
H --> J[Priority Queue]
I --> J
C --> K[buildHeap]
K --> L[Heap sort 与复杂度]
F --> M[updateElem]
G --> M
J --> N[Top K 与 K 路归并]
J --> O[双堆与图算法]
L --> P[lab heaps 完整实践]
1. 为什么需要 Heap
普通队列遵循 FIFO：
1
先进来的元素先出去
但很多问题需要的是：
无论元素什么时候进入，都优先处理当前优先级最高的元素。
例如：
1
2
3
4
5
操作系统调度高优先级任务
网络路由选择下一条最短距离
Dijkstra 算法取当前距离最小的节点
事件循环处理最近要发生的事件
任务系统处理紧急任务
假设元素和优先级依次到来：
1
A(2), B(5), C(1), D(4)
如果数字越小优先级越高，取出顺序应该是：
1
C(1), A(2), D(4), B(5)
这不是普通 Queue，而是 Priority Queue（优先队列）。
1.1 直接使用数组有什么问题
如果每次取最小值，就扫描整个数组：
1
2
peek minimum：O(n)
pop minimum：找到最小值 O(n)，删除后可能移动元素 O(n)
如果始终让数组有序：
1
2
3
peek：O(1)
插入：O(n)
删除：O(1) 或 O(n)，取决于维护方式
Heap 的目标是折中：
1
2
3
peek 最高优先级：O(1)
push：O(log n)
pop 最高优先级：O(log n)
2. Heap 是什么
Heap 是一种抽象数据结构，核心要求是：
每个 parent 的优先级不低于它的 child。
如果数字越小优先级越高，就是 min-heap：
1
parent <= child
如果数字越大优先级越高，就是 max-heap：
1
parent >= child
2.1 Min-heap 示例
graph TD
A[1] --> B[3]
A --> C[2]
B --> D[8]
B --> E[5]
C --> F[4]
C --> G[7]
每条 parent-child 边都满足：
1
2
3
1 <= 3, 1 <= 2
3 <= 8, 3 <= 5
2 <= 4, 2 <= 7
因此根节点一定是整个堆中优先级最高的元素，也就是 min-heap 中的最小值。
2.2 Heap 不是 BST
这是初学时最容易混淆的地方。
BST 要求：
1
2
左子树所有 key < 当前节点
右子树所有 key > 当前节点
Heap 只要求：
1
parent 与 child 之间满足优先级关系
例如下面是合法 min-heap：
1
2
3
4
5
1
/ \
3 2
/ \
8 5
但它不是 BST：数值 3 位于根 1 的左边，却有 3 > 1，已经违反 BST 的“左子树所有 key 小于当前 key”。Heap 只关心 parent 的优先级，不支持通过中序遍历得到排序序列。
可以记成：
1
2
BST：全子树有序
Heap：局部 parent-child 有序
3. 为什么使用完全二叉树
课程中的 Binary Heap 具有两个条件：
1
2
形状条件：是一棵 complete binary tree
顺序条件：满足 min-heap 或 max-heap 的 heap property
完全二叉树的最后一层从左到右连续填充，没有中间空洞。因此可以按层序放进数组，不需要保存 left/right 指针。
树：
1
2
3
4
5
1
/ \
3 2
/ \ /
8 5 4
数组：
1
2
index： 0 1 2 3 4 5
value： 1 3 2 8 5 4
这也是 Heap 和红黑树、AVL 不同的地方：
1
2
AVL / 红黑树：通常需要节点指针，因为形状不固定
Binary Heap：完全形状固定，数组更简单、更紧凑、局部性更好
3.1 为什么完全二叉树的高度是 O(log n)
如果根所在层记为第 0 层，那么第 i 层最多有：
1
2^i 个节点
高度为 h 的满二叉树共有：
1
1 + 2 + 4 + ... + 2^h = 2^(h + 1) - 1
完全二叉树除了最后一层以外都被填满，因此节点数 n 与 2^h 同阶：
1
h = Θ(log n)
4. 0-based 数组下标公式
设节点下标为 i，使用 0-based index：
1
2
3
left child = 2 * i + 1
right child = 2 * i + 2
parent = (i - 1) / 2 // i > 0，整数除法
例如下标为 1 的节点：
1
2
3
left = 2 * 1 + 1 = 3
right = 2 * 1 + 2 = 4
parent = (1 - 1) / 2 = 0
数组下标关系可以直接写成辅助函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static constexpr std::size_t leftChild(std::size_t index) noexcept
{
return 2 * index + 1;
}
static constexpr std::size_t rightChild(std::size_t index) noexcept
{
return 2 * index + 2;
}
static constexpr std::size_t parent(std::size_t index) noexcept
{
return (index - 1) / 2;
}
parent(0) 没有意义，因为根节点没有 parent。实际调用前必须保证：
1
index > 0
如果使用 1-based 数组，则公式会变成：
1
2
3
left child = 2 * i
right child = 2 * i + 1
parent = i / 2
两种都可以，关键是整个实现统一。本文和 std::vector 代码统一使用 0-based。
5. Heap 的不变量
实现 Heap 时，始终维护两个不变量：
5.1 形状不变量
数组中的元素对应一棵完全二叉树：
1
2
3
不能在数组中间留下空洞
新元素只能放在末尾
删除根后要用最后一个元素补到根
5.2 顺序不变量
对于 min-heap：
1
每个 parent <= 它的每个 child
对于 max-heap：
1
每个 parent >= 它的每个 child
注意：执行一次 push 或 pop 时，通常只会暂时破坏一条从节点向上的或向下的路径；修复算法只需要沿这条路径移动。
6. 用比较器同时支持 min-heap 和 max-heap
不要分别复制两套 min-heap、max-heap 代码。使用比较器表示“谁的优先级更高”：
1
Compare higherPriority;
默认使用：
1
std::less<T>
对于整数：
1
std::less<int> {}(2, 5) == true
所以数字越小优先级越高，得到 min-heap。
如果使用：
1
std::greater<int>
则数字越大优先级越高，得到 max-heap。
6.1 最终公共接口
先看使用者需要的功能：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T, typename Compare = std::less<T>>
class BinaryHeap
{
public:
BinaryHeap() = default;
explicit BinaryHeap(const std::vector<T>& values);
bool empty() const noexcept;
std::size_t size() const noexcept;
const T& peek() const;
void push(const T& value);
void push(T&& value);
void pop();
void updateElem(std::size_t index, const T& value);
private:
std::vector<T> data_;
Compare higherPriority_ {};
};
peek() 只查看根节点，不删除；pop() 删除根节点；push() 把新元素加入堆。
7. heapifyUp：插入后的向上修复
7.1 为什么插入只能放在数组末尾
完全二叉树要求新节点占据下一个层序位置，因此新元素只能先放到 vector 尾部：
1
2
3
4
5
6
7
旧堆： 插入 1 后：
3 3
/ \ / \
5 4 5 4
/ / \
8 8 1 <- 新节点先放末尾
形状保持了完全，但顺序可能被破坏：
1
1 < 5
这里应该比较新节点 1 与它的父节点 5。节点 1 和节点 8 是兄弟节点，堆序性质不要求兄弟节点之间满足大小关系。
7.2 向上交换
新节点只可能和 parent 产生冲突，因此反复比较它与 parent：
1
2
3
如果新节点优先级高于 parent：交换
否则：停止
到达根：停止
对于 min-heap，插入 1：
1
2
3
4
5
6
7
8
9
初始数组：[3, 5, 4, 8, 1]
1 与父节点 5 比较：交换
[3, 1, 4, 8, 5]
1 与新的父节点 3 比较：交换
[1, 3, 4, 8, 5]
1 到达根
1 从下标 4 开始，它的父节点下标是 (4 - 1) / 2 = 1，所以第一次比较对象是下标 1 的元素 5。节点 8 位于下标 3，它是 1 的兄弟节点，不在 heapifyUp 的父节点路径上。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
void heapifyUp(std::size_t index)
{
while (index > 0) {
std::size_t p = parent(index);
if (!higherPriority_(data_[index], data_[p])) {
break;
}
std::swap(data_[index], data_[p]);
index = p;
}
}
循环结束时，当前节点与 parent 的顺序已经正确；由于路径外的其他节点没有变化，整个堆恢复合法。
7.3 push
1
2
3
4
5
void push(const T& value)
{
data_.push_back(value);
heapifyUp(data_.size() - 1);
}
逻辑是：
1
2
1. 末尾加入，维护 complete shape
2. 向上交换，恢复 heap property
8. heapifyDown：删除后的向下修复
8.1 为什么删除根后要用最后一个元素补位
Heap 的最高优先级元素在根，也就是数组下标 0：
1
data_[0]
删除它后，不能让数组中间产生空洞，所以把最后一个元素移动到根：
1
2
3
4
5
6
7
8
9
10
11
删除前：
1
/ \
3 2
/
8
删除 1，将末尾 8 放到根：
8
/ \
3 2
形状仍然是完全二叉树，但顺序可能被破坏：
1
2
8 > 3
8 > 2
8.2 为什么要和更高优先级的孩子交换
如果 parent 同时有两个孩子，不能随便选择一个交换。min-heap 应该选择更小的孩子，max-heap 应该选择更大的孩子。
否则可能出现：
1
2
parent 与选择的 child 合法
但 parent 与另一个更高优先级 child 仍然冲突
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void heapifyDown(std::size_t index)
{
while (true) {
std::size_t best = index;
std::size_t left = leftChild(index);
std::size_t right = rightChild(index);
if (left < data_.size()
&& higherPriority_(data_[left], data_[best])) {
best = left;
}
if (right < data_.size()
&& higherPriority_(data_[right], data_[best])) {
best = right;
}
if (best == index) {
break;
}
std::swap(data_[index], data_[best]);
index = best;
}
}
8.3 pop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pop()
{
if (data_.empty()) {
throw std::out_of_range("pop on empty heap");
}
if (data_.size() == 1) {
data_.pop_back();
return;
}
data_[0] = std::move(data_.back());
data_.pop_back();
heapifyDown(0);
}
逻辑是：
1
2
3
1. 保存/移除根
2. 最后一个元素补到根
3. 从根向下与更高优先级 child 交换
9. 一份完整的基础 BinaryHeap
下面这份代码把前面的接口、下标辅助函数、向上修复、向下修复和构造函数连在一起。构造函数中的 buildHeap() 会在下一节详细解释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <algorithm>
#include <cstddef>
#include <functional>
#include <stdexcept>
#include <utility>
#include <vector>
template <typename T, typename Compare = std::less<T>>
class BinaryHeap
{
private:
std::vector<T> data_;
Compare higherPriority_ {};
static constexpr std::size_t leftChild(
std::size_t index) noexcept
{
return 2 * index + 1;
}
static constexpr std::size_t rightChild(
std::size_t index) noexcept
{
return 2 * index + 2;
}
static constexpr std::size_t parent(
std::size_t index) noexcept
{
return (index - 1) / 2;
}
void heapifyUp(std::size_t index)
{
while (index > 0) {
const std::size_t p = parent(index);
if (!higherPriority_(data_[index], data_[p])) {
break;
}
std::swap(data_[index], data_[p]);
index = p;
}
}
void heapifyDown(std::size_t index)
{
while (true) {
std::size_t best = index;
const std::size_t left = leftChild(index);
const std::size_t right = rightChild(index);
if (left < data_.size()
&& higherPriority_(data_[left], data_[best])) {
best = left;
}
if (right < data_.size()
&& higherPriority_(data_[right], data_[best])) {
best = right;
}
if (best == index) {
break;
}
std::swap(data_[index], data_[best]);
index = best;
}
}
void buildHeap()
{ //从最后一个非叶节点开始，依次对每个节点做下沉
if (data_.empty()) {
return;
}
// 最后一个非叶节点的下标是 size / 2 - 1。
for (std::size_t i = data_.size() / 2; i > 0; --i) {
heapifyDown(i - 1);//i 的左右子树已经是合法的堆。它只负责把 i 这个节点往下调整。
}
}
public:
BinaryHeap() = default;
explicit BinaryHeap(const std::vector<T>& values)
: data_(values)
{
buildHeap();
}
bool empty() const noexcept
{
return data_.empty();
}
std::size_t size() const noexcept
{
return data_.size();
}
const T& peek() const
{
if (data_.empty()) {
throw std::out_of_range("peek on empty heap");
}
return data_.front();
}
void push(const T& value)
{
data_.push_back(value);
heapifyUp(data_.size() - 1);
}
void push(T&& value)
{
data_.push_back(std::move(value));
heapifyUp(data_.size() - 1);
}
void pop()
{
if (data_.empty()) {
throw std::out_of_range("pop on empty heap");
}
if (data_.size() == 1) {
data_.pop_back();
return;
}
data_.front() = std::move(data_.back());
data_.pop_back();
heapifyDown(0);
}
void updateElem(std::size_t index, const T& value)
{
if (index >= data_.size()) {
throw std::out_of_range("heap index out of range");
}
data_[index] = value;
if (index > 0
&& higherPriority_(data_[index], data_[parent(index)])) {
heapifyUp(index); //新节点优先级更高，上浮
} else {
heapifyDown(index); //新节点优先级更低，下沉
}
}
};
10. 当前阶段的复杂度
设堆中有 n 个元素。完全二叉树高度为：
1
O(log n)
因此：
| 操作 | 复杂度 | 原因 |
|---|---|---|
peek | O(1) | 根在 data_[0] |
push | O(log n) | 最多向上走树高 |
pop | O(log n) | 最多向下走树高 |
empty | O(1) | vector 状态 |
size | O(1) | vector 状态 |
| 单次元素交换 | O(1) | 只交换两个数组位置 |
当前基础实现的核心不变量是：
1
2
3
push 后：数组仍表示完全二叉树，heap property 恢复
pop 后：数组仍表示完全二叉树，heap property 恢复
peek 永远返回根，也就是最高优先级元素
11. lab_heaps 要完成什么
实验实现的是数组版 min/max heap，允许选择 0-based 或 1-based 数组，但必须全程统一。
主要接口和任务：
1
2
3
4
5
6
7
8
9
10
11
12
13
root()：返回根元素的数组下标
leftChild(index)：返回左孩子下标
rightChild(index)：返回右孩子下标
parent(index)：返回父节点下标
empty()：判断堆是否为空
hasAChild(index)：判断是否存在孩子
maxPriorityChild(index)：返回两个孩子中优先级更高的那个
heapifyDown(index)：向下恢复 heap property
heapifyUp(index)：向上恢复 heap property
push(element)：末尾加入后 heapifyUp
pop()：移除根并 heapifyDown
peek()：查看根
updateElem(index, element)：修改元素后向上或向下修复
实验框架提供了 heapifyUp() 作为参考；你需要重点实现下标关系、maxPriorityChild()、heapifyDown()、构造函数、pop()、peek()、push() 和 updateElem()。
这里的 maxPriorityChild 名称不代表一定使用数值最大者。它实际表示：
1
根据 higherPriority 比较器，返回两个孩子中优先级更高的那个
例如 min-heap 中应该返回数值更小的孩子，max-heap 中应该返回数值更大的孩子。
12. buildHeap：一次把无序数组变成 Heap
12.1 为什么不能只把数组当成已经合法的 Heap
假设收到无序数组：
1
[9, 4, 7, 1, 3, 6, 2]
它虽然能按完全二叉树的形状解释：
graph TD
A[9] --> B[4]
A --> C[7]
B --> D[1]
B --> E[3]
C --> F[6]
C --> G[2]
但它不是 min-heap，因为根 9 比孩子 4 和 7 都大。构造函数复制数组以后，还必须恢复 heap property。
最直接的办法是从空 Heap 开始，逐个调用 push()：
1
2
3
for (const T& value : values) {
push(value);
}
每次 push() 最坏需要 O(log n)，因此总复杂度是：
1
O(n log n)
这个方法正确，但不是最优的建堆方式。
12.2 叶节点天然已经是合法 Heap
一个只有自己的节点没有孩子，因此不可能违反 parent-child 顺序。也就是说：
所有叶节点本身都已经是一棵合法的 Heap。
在 0-based 数组中：
1
2
第一个叶节点下标 = n / 2
最后一个非叶节点 = n / 2 - 1
因此不需要从最后一个元素开始修复，只需从最后一个非叶节点倒着执行 heapifyDown()：
1
2
3
4
5
6
void buildHeap()
{
for (std::size_t i = data_.size() / 2; i > 0; --i) {
heapifyDown(i - 1);
}
}
这里写成 i > 0 后访问 i - 1，是为了避免 std::size_t 的无符号下溢。下面这种循环有风险：
1
2
3
4
// 错误倾向：i 到 0 后再 --i，会变成一个非常大的无符号数。
for (std::size_t i = data_.size() / 2 - 1; i >= 0; --i) {
heapifyDown(i);
}
12.3 为什么要从下往上
heapifyDown(i) 能正确工作的前提是：
i的左右子树已经分别是合法 Heap。
从最后一个非叶节点倒着处理时，它的孩子都是叶节点，所以前提成立。处理完它以后，以它为根的子树也成为合法 Heap。继续向前处理父节点时，父节点的左右子树已经处理完毕。
这是一个自底向上的过程：
flowchart BT
L[叶节点天然合法] --> P[修复最底层父节点]
P --> U[修复更上一层父节点]
U --> R[修复根节点]
R --> H[整个数组成为 Heap]
12.4 buildHeap 为什么是 O(n)
乍看之下，一共有 O(n) 个节点，每次 heapifyDown() 又可能是 O(log n)，似乎应当是 O(n log n)。这个估计虽然是一个合法上界，但不够紧，因为大多数节点根本走不了树高那么多层。
在完全二叉树中大致有：
1
2
3
4
n / 2 个节点位于叶层：向下 0 层
n / 4 个节点距离叶层 1 层：最多向下 1 层
n / 8 个节点距离叶层 2 层：最多向下 2 层
...
所以总工作量近似为：
1
2
3
4
5
(n/4) * 1 + (n/8) * 2 + (n/16) * 3 + ...
= n * (1/4 + 2/8 + 3/16 + ...)
= O(n)
括号里的无穷级数会收敛到一个常数，因此：
1
2
自底向上 buildHeap：O(n)
逐个 push 建堆：O(n log n)
注意，buildHeap 是 O(n)，并不表示单次 heapifyDown 变成了 O(1)；是因为所有节点的实际下沉距离加起来只有线性规模。
12.5 建堆示例
对下面的数组构造 min-heap：
1
2
[9, 4, 7, 1, 3, 6, 2]
n = 7，最后一个非叶节点 = 7 / 2 - 1 = 2
依次处理下标 2、1、0：
1
2
3
4
5
6
7
8
9
i = 2：7 与孩子 6、2 比较，和 2 交换
[9, 4, 2, 1, 3, 6, 7]
i = 1：4 与孩子 1、3 比较，和 1 交换
[9, 1, 2, 4, 3, 6, 7]
i = 0：9 与孩子 1、2 比较，和 1 交换
继续让 9 与 4、3 比较，和 3 交换
[1, 3, 2, 4, 9, 6, 7]
最终每个 parent 都不大于它的孩子。
13. updateElem：修改元素后怎样恢复 Heap
13.1 修改后只可能向一个方向出问题
修改 data_[index] 后，完全二叉树的形状没有变化，只有顺序可能被破坏。
以 min-heap 为例：
- 新值变小，可能比 parent 更小，需要
heapifyUp； - 新值变大，可能比某个 child 更大，需要
heapifyDown； - 新值仍处于合法范围，两个修复函数都会很快停止。
真正可靠的判断不是直接使用数值的 < 或 >，而是继续使用统一的 higherPriority_ 比较器。
13.2 根据 parent 判断方向
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void updateElem(std::size_t index, const T& value)
{
if (index >= data_.size()) {
throw std::out_of_range("heap index out of range");
}
data_[index] = value;
if (index > 0
&& higherPriority_(data_[index], data_[parent(index)])) {
heapifyUp(index);
} else {
heapifyDown(index);
}
}
为什么只判断 parent 就够了？
- 如果新节点优先级高于 parent，问题一定在上方，应向上修复；
- 否则它与 parent 合法，但可能低于孩子，应向下修复。
合法 Heap 中，修改之前节点位于 parent 和 children 的优先级之间。一次修改不可能既需要越过 parent，又需要越过 child，所以只需要选择一个方向。
13.3 另一种写法：比较新旧值
也可以先保存旧值：
1
2
3
4
5
6
7
8
T old = data_[index];
data_[index] = value;
if (higherPriority_(value, old)) {
heapifyUp(index);
} else {
heapifyDown(index);
}
这个写法要求能复制 T，而且“新旧元素的相对优先级”必须能明确判断。根据 parent 检查通常更直接，也避免额外保存一份旧值。
13.4 复杂度与实际用途
updateElem() 最多沿根到叶的一条路径移动：
1
2
时间：O(log n)
额外空间：迭代写法 O(1)
典型用途包括：
1
2
3
4
Dijkstra 的 decrease-key
任务优先级发生变化
定时事件的触发时间改变
调度系统更新任务权重
标准 std::priority_queue 不提供按下标更新元素的接口。算法中常见的替代方法是把新状态再次压入堆，并在弹出旧状态时将其识别为 stale entry 后跳过。
14. Heap Sort
14.1 排升序为什么要建 max-heap
如果希望最终得到升序数组，可以先把数组构造成 max-heap。此时根是当前最大值：
1
2
3
4
5
1. 根与有效区间的最后一个元素交换
2. 最大值被放到最终位置
3. 有效 Heap 的大小减 1
4. 对根执行 heapifyDown
5. 重复直到只剩一个元素
例如：
1
2
3
4
5
6
7
max-heap: [9, 7, 6, 4, 3, 1, 2]
交换根和末尾：
[2, 7, 6, 4, 3, 1, | 9]
只在竖线左边恢复 max-heap：
[7, 4, 6, 2, 3, 1, | 9]
右侧区域已经排好，后续不再属于 Heap。
14.2 完整的原地 Heap Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cstddef>
#include <vector>
template <typename T>
void heapSort(std::vector<T>& values)
{
const std::size_t n = values.size();
auto heapifyDown = [&](std::size_t start,
std::size_t heapSize) {
std::size_t current = start;
while (true) {
std::size_t largest = current;
const std::size_t left = 2 * current + 1;
const std::size_t right = 2 * current + 2;
if (left < heapSize && values[largest] < values[left]) {
largest = left;
}
if (right < heapSize && values[largest] < values[right]) {
largest = right;
}
if (largest == current) {
return;
}
std::swap(values[current], values[largest]);
current = largest;
}
};
// 自底向上建立 max-heap。
for (std::size_t i = n / 2; i > 0; --i) {
heapifyDown(i - 1, n);
}
// 每次把当前最大值放到有效区间末尾。
for (std::size_t heapSize = n; heapSize > 1; --heapSize) {
std::swap(values[0], values[heapSize - 1]);
heapifyDown(0, heapSize - 1);
}
}
这里用 lambda 把只服务于 heapSort() 的辅助逻辑限制在函数内部。也可以把它写成普通的私有辅助函数。
14.3 Heap Sort 的性质
| 性质 | 结论 |
|---|---|
| 建堆 | O(n) |
| 反复取最大值 | n - 1 次，每次 O(log n) |
| 总时间 | O(n log n)，最好、平均、最坏都一样 |
| 额外空间 | O(1)，可以原地完成 |
| 稳定性 | 不稳定 |
“不稳定”表示相等元素的原有相对顺序可能改变。实际工程中通常优先使用 std::sort；Heap Sort 更重要的价值是理解 Heap、原地排序和复杂度保证。
15. lab_heaps 逐函数完整实现
15.1 先确认课程框架的约定
课程允许 0-based 或 1-based，但必须统一。本文完整答案选择 0-based：
1
2
3
4
root = 0
left = 2i + 1
right = 2i + 2
parent = (i - 1) / 2
课程框架与前文教学版 BinaryHeap 有两个接口差异：
- 课程的
pop()返回被移除的最高优先级元素； updateElem(idx, elem)的idx是相对于 Heap 根的逻辑下标。
0-based 实现中，逻辑下标与 _elems 的实际下标相同。
15.2 下标辅助函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::size_t root() const
{
return 0;
}
std::size_t leftChild(std::size_t currentIdx) const
{
return 2 * currentIdx + 1;
}
std::size_t rightChild(std::size_t currentIdx) const
{
return 2 * currentIdx + 2;
}
std::size_t parent(std::size_t currentIdx) const
{
return (currentIdx - 1) / 2;
}
不要对根调用 parent(0)。无符号整数的 0 - 1 会下溢；heapifyUp() 必须先检查 currentIdx != root()。
15.3 hasAChild 与 maxPriorityChild
完全二叉树中，如果左孩子不存在，右孩子也不可能单独存在。因此：
1
2
3
4
bool hasAChild(std::size_t currentIdx) const
{
return leftChild(currentIdx) < _elems.size();
}
选择最高优先级孩子时先处理“只有左孩子”的情况：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::size_t maxPriorityChild(std::size_t currentIdx) const
{
const std::size_t left = leftChild(currentIdx);
const std::size_t right = rightChild(currentIdx);
if (right >= _elems.size()) {
return left;
}
if (higherPriority(_elems[left], _elems[right])) {
return left;
}
return right;
}
这里的 maxPriorityChild 是“优先级最大”，不是“数值最大”。对于默认 min-heap，它会返回数值较小的孩子。
15.4 heapifyDown 与 heapifyUp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void heapifyDown(std::size_t currentIdx)
{
while (hasAChild(currentIdx)) {
const std::size_t child = maxPriorityChild(currentIdx);
if (!higherPriority(_elems[child], _elems[currentIdx])) {
break;
}
std::swap(_elems[currentIdx], _elems[child]);
currentIdx = child;
}
}
void heapifyUp(std::size_t currentIdx)
{
while (currentIdx != root()) {
const std::size_t p = parent(currentIdx);
if (!higherPriority(_elems[currentIdx], _elems[p])) {
break;
}
std::swap(_elems[currentIdx], _elems[p]);
currentIdx = p;
}
}
课程可能提供递归版 heapifyUp()，循环版与递归版的逻辑等价。循环版的额外空间为 O(1)。
15.5 构造函数
1
2
3
4
5
6
7
8
9
heap() = default;
explicit heap(const std::vector<T>& elems)
: _elems(elems)
{
for (std::size_t i = _elems.size() / 2; i > 0; --i) {
heapifyDown(i - 1);
}
}
构造函数不能只复制 _elems，因为输入 vector 不保证已经满足 heap property。
15.6 peek、push 和 pop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
T peek() const
{
if (empty()) {
throw std::out_of_range("peek on empty heap");
}
return _elems[root()];
}
void push(const T& elem)
{
_elems.push_back(elem);
heapifyUp(_elems.size() - 1);
}
T pop()
{
if (empty()) {
throw std::out_of_range("pop on empty heap");
}
T result = std::move(_elems[root()]);
if (_elems.size() == 1) {
_elems.pop_back();
return result;
}
_elems[root()] = std::move(_elems.back());
_elems.pop_back();
heapifyDown(root());
return result;
}
先保存根是因为课程接口要求返回被删除的元素。单元素分支可以避免对同一个元素做无意义的自移动赋值，也不必再调用 heapifyDown()。对于上面这份“先补根、再 pop_back()”的具体代码，它不是为了防止“删除后再写根越界”；如果采用“先 pop_back()、再写根”的顺序，才会产生越界问题。
15.7 updateElem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void updateElem(const std::size_t& idx, const T& elem)
{
if (idx >= _elems.size()) {
throw std::out_of_range("heap index out of range");
}
_elems[idx] = elem;
if (idx != root()
&& higherPriority(_elems[idx], _elems[parent(idx)])) {
heapifyUp(idx);
} else {
heapifyDown(idx);
}
}
下面的版本使用 higherPriority(a, b) 表示 a 的优先级高于 b。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <algorithm>
#include <cstddef>
#include <functional>
#include <stdexcept>
#include <utility>
#include <vector>
template <typename T, typename Compare = std::less<T>>
class heap
{
private:
std::vector<T> _elems;
Compare higherPriority {};
std::size_t root() const
{
return 0;
}
std::size_t leftChild(std::size_t index) const
{
return 2 * index + 1;
}
std::size_t rightChild(std::size_t index) const
{
return 2 * index + 2;
}
std::size_t parent(std::size_t index) const
{
return (index - 1) / 2;
}
bool hasAChild(std::size_t index) const
{
return leftChild(index) < _elems.size();
}
std::size_t maxPriorityChild(std::size_t index) const
{
const std::size_t left = leftChild(index);
const std::size_t right = rightChild(index);
if (right >= _elems.size()
|| higherPriority(_elems[left], _elems[right])) {
return left;
}
return right;
}
void heapifyUp(std::size_t index)
{
while (index != root()) {
const std::size_t p = parent(index);
if (!higherPriority(_elems[index], _elems[p])) {
return;
}
std::swap(_elems[index], _elems[p]);
index = p;
}
}
void heapifyDown(std::size_t index)
{
while (hasAChild(index)) {
const std::size_t child = maxPriorityChild(index);
if (!higherPriority(_elems[child], _elems[index])) {
return;
}
std::swap(_elems[index], _elems[child]);
index = child;
}
}
public:
heap() = default;
explicit heap(const std::vector<T>& elems)
: _elems(elems)
{
for (std::size_t i = _elems.size() / 2; i > 0; --i) {
heapifyDown(i - 1);
}
}
bool empty() const noexcept
{
return _elems.empty();
}
std::size_t size() const noexcept
{
return _elems.size();
}
T peek() const
{
if (empty()) {
throw std::out_of_range("peek on empty heap");
}
return _elems[root()];
}
void push(const T& elem)
{
_elems.push_back(elem);
heapifyUp(_elems.size() - 1);
}
T pop()
{
if (empty()) {
throw std::out_of_range("pop on empty heap");
}
T result = std::move(_elems[root()]);
if (_elems.size() == 1) {
_elems.pop_back();
return result;
}
_elems[root()] = std::move(_elems.back());
_elems.pop_back();
heapifyDown(root());
return result;
}
void updateElem(const std::size_t& index, const T& elem)
{
if (index >= _elems.size()) {
throw std::out_of_range("heap index out of range");
}
_elems[index] = elem;
if (index != root()
&& higherPriority(_elems[index], _elems[parent(index)])) {
heapifyUp(index);
} else {
heapifyDown(index);
}
}
};
16 std::priority_queue
需要头文件：
1
#include <queue>
默认声明：
1
std::priority_queue<int> heap; //默认是大顶堆
默认相当于：
1
2
3
4
5
std::priority_queue<
int,
std::vector<int>,
std::less<int>
> heap;
它是 max-heap，top() 返回最大值：
1
2
3
4
5
heap.push(3);
heap.push(8);
heap.push(5);
heap.top(); // 8
这是一个常见易错点：
1
2
std::less<T> -> max-heap
std::greater<T> -> min-heap
这与本文前面自己实现的 BinaryHeap 恰好相反：前面的教学类把比较器明确解释成 higherPriority(a, b)，所以 std::less<T> 代表较小者优先，得到 min-heap；标准库 priority_queue 对 Compare 采用自己的接口语义，所以默认 std::less<T> 得到 max-heap。使用时必须以具体类对比较器的定义为准，不能只看 less/greater 猜测。
最小堆：
1
2
3
4
5
6
7
8
9
#include <functional>
#include <queue>
#include <vector>
std::priority_queue<
int,
std::vector<int>,
std::greater<int>
> minHeap;
16.3 为什么比较器看起来“反了”
priority_queue 的 Compare 可以理解为：
如果
compare(a, b)为 true，那么在队列的优先级顺序中，a 排在 b 后面。
使用：
1
std::less<int>
时：
1
2
3
less(3, 8) == true
所以 3 的优先级排在 8 后面
top 是 8
使用：
1
std::greater<int>
时：
1
2
3
greater(8, 3) == true
所以 8 的优先级排在 3 后面
top 是 3
不要只背“大于号是小顶堆”，要理解 top() 是没有任何其他元素被 Compare 排在它前面的那个元素。
16.4 自定义类型的比较器
例如任务中数字越小优先级越高：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Task
{
int id;
int priority;
};
struct CompareTask
{
bool operator()(const Task& left,
const Task& right) const
{
return left.priority > right.priority;
}
};
std::priority_queue<
Task,
std::vector<Task>,
CompareTask
> tasks;
这里 left.priority > right.priority 表示：priority 数字更大的任务排在后面，因此数字最小的任务位于 top()。
也可以使用 lambda：
1
2
3
4
5
6
7
8
9
auto compare = [](const Task& left, const Task& right) {
return left.priority > right.priority;
};
std::priority_queue<
Task,
std::vector<Task>,
decltype(compare)
> tasks(compare);
16.5 priority_queue 的接口和复杂度
1
2
3
4
5
6
heap.push(value); // O(log n)
heap.emplace(args); // O(log n)
heap.top(); // O(1)，返回 const reference
heap.pop(); // O(log n)，不返回被删除元素
heap.empty(); // O(1)
heap.size(); // O(1)
若要取得并删除 top：
1
2
int value = heap.top();
heap.pop();
pop() 不直接返回元素，与 stack/queue 的接口风格相同。将读取和修改拆开，也避免“元素返回过程中抛异常，而容器已经被修改”等接口设计问题。
16.6 priority_queue 是容器适配器
std::priority_queue 和 std::stack/std::queue 一样，是 container adaptor，而不是直接暴露底层存储的普通容器。
默认底层容器是：
1
std::vector<T>
因为 binary heap 需要：
1
2
3
末尾高效插入删除
通过下标随机访问 parent 和 children
连续数组保存完全二叉树
底层容器必须支持随机访问以及 front/push_back/pop_back 等操作，因此 std::list 不适合作为二叉堆底层。
priority_queue 不提供普通迭代器，也不支持直接搜索和删除任意元素。
16.7 Heap 不等于有序数组
合法 min-heap 数组可能是：
1
[1, 3, 2, 8, 5, 4, 7]
它不是完整升序：
1
3 > 2
但它满足所有 parent 不大于 child。
因此：
| 操作 | Binary Heap |
|---|---|
| 查看最小/最大值 | O(1) |
| 删除最小/最大值 | O(log n) |
| 查找任意指定值 | O(n) |
| 判断第 k 个数组元素的全局排名 | 不能直接判断 |
| 完整排序输出 | 连续 pop，O(n log n) |
16.8 Top K 是最常见的 Heap 模型
找第 k 大或最大的 k 个元素
维护一个大小最多为 k 的 min-heap：
1
2
3
遍历每个元素
加入 min-heap
如果 size > k，弹出当前最小值
最后堆里保留最大的 k 个数，堆顶是其中最小的，也就是全局第 k 大。
复杂度：
1
2
时间：O(n log k)
空间：O(k)
为什么找最大 k 个却使用 min-heap？
堆顶保存“当前入选者中最弱的那个”。遇到更好的候选时，才能快速把最弱者淘汰。
同理：
1
2
维护最大的 k 个：大小为 k 的 min-heap
维护最小的 k 个：大小为 k 的 max-heap
16.9 高频 Heap 算法题型
第 k 大/小、Top K 高频元素
1
2
3
LeetCode 215：数组中的第 K 个最大元素
LeetCode 347：前 K 个高频元素
LeetCode 703：数据流中的第 K 大元素
核心是维护固定大小 k 的堆。
K 路归并
1
2
3
LeetCode 23：合并 K 个升序链表
合并多个有序文件或数据流
外部排序
把每一路当前最小元素放进 min-heap。每取出一个，就把它所在序列的下一个元素加入堆。
复杂度通常是：
1
2
3
总元素数 N，序列数 k
时间 O(N log k)
空间 O(k)
数据流中位数
1
LeetCode 295：数据流的中位数
使用两个堆：
1
2
max-heap：保存较小的一半，top 是小半区最大值
min-heap：保存较大的一半，top 是大半区最小值
始终维护两个堆大小差不超过 1。
调度与区间问题
1
2
3
4
会议室分配
任务调度
CPU 任务优先级
事件模拟
通常按时间排序后，用 min-heap 保存“最早结束时间”或“下一次事件时间”。
图算法
1
2
3
Dijkstra：取当前暂定距离最小节点
Prim：取连接已选集合的最小边
A*：取估价函数最小状态
在 C++ priority_queue 中通常无法直接 decrease-key。常见做法是把更新后的新状态再次 push，pop 时跳过过期记录：
1
2
3
4
5
auto [distance, node] = heap.top();
heap.pop();
if (distance != best[node]) {
continue; // stale entry