Chapter 31: Heap Algorithms
核心问题与阅读主线
STL 堆算法仅在随机访问区间 [first, last) 上重排已有元素以维护堆不变量,不管理容器容量与生命周期。串联 make_heap、push_heap、pop_heap、sort_heap 与检查算法时,核心是把控调用前提、比较器方向以及有效堆前缀边界。
全章共用代码样本(下文各节持续拆解)
下面的 std::vector<int> 示例贯穿本章,演示从建堆、入堆、出堆到破坏定位与排序的完整路径(标准定义见 heap operations:默认 std::less 下 comp(parent, child) 为 false,堆顶为最大元素):
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> scores{4, 1, 7, 3, 9, 2};
std::make_heap(scores.begin(), scores.end());
scores.push_back(8);
std::push_heap(scores.begin(), scores.end());
std::pop_heap(scores.begin(), scores.end());
int top_score = scores.back();
scores.pop_back();
auto broken = std::is_heap_until(scores.begin(), scores.end());
bool valid = broken == scores.end();
std::sort_heap(scores.begin(), scores.end());
std::cout << top_score << ' ' << valid << '\n';
}
边界分工决定区间状态:push_back / pop_back 改变 vector 真实长度,而 push_heap / pop_heap 只重排 [first, last);尾部位置在 pop_heap 中承接移出的顶值,在 sort_heap 中积累有序后缀并消耗原堆不变量。
31.1 heap 数据结构
STL 堆是在连续逻辑数组上模拟的完全二叉树,依赖随机访问迭代器的下标算术定位父子关系,无需节点保存 parent、left 或 right 指针。
关键事实
- 下标映射:根节点为
0;位置i的左孩子为2 * i + 1,右孩子为2 * i + 2,父节点为(i - 1) / 2。 - 比较器方向:合法堆要求所有父子满足
comp(parent, child) == false——std::less<T>使parent < child为false(parent >= child,最大堆),std::greater<T>使parent > child为false(parent <= child,最小堆)。
因为父子跳转依赖 first + n、last - first 等常数时间算术,底层容器的能力决定了它能否承接堆算法:
| 底层容器 | 随机访问能力 | 适用性说明 |
|---|---|---|
std::vector | 支持 | 连续内存、缓存局部性最佳,std::priority_queue 默认底层容器 |
std::deque | 支持 | 分段连续存储,支持 O(1) 下标跳转与尾部插删 |
std::list | 不支持(不可用) | 双向迭代器无法 O(1) 计算 first + child_index |
下面这段合法最大堆演示了父子局部序的校验方式:
std::vector<int> heap{9, 5, 7, 1, 3, 4, 6};
// 索引 0 的孩子是 1、2:9 >= 5,9 >= 7
// 索引 1 的孩子是 3、4:5 >= 1,5 >= 3
// 索引 2 的孩子是 5、6:7 >= 4,7 >= 6
bool ok = std::is_heap(heap.begin(), heap.end());
边界与误区
堆只保证根节点为最高优先级元素及父子间的局部顺序,对兄弟、同层或跨子树节点没有任何全局序承诺;{9, 5, 7, 1, 3, 4, 6} 是合法最大堆,但整体既非升序也非降序。
31.2 make_heap
std::make_heap 原地把 [first, last) 重排成合法堆,不分配节点也不改变容器大小。经典实现从最后一个非叶子节点 (n - 2) / 2 自底向上向根节点推进,沿较高优先级孩子方向下沉(参见 std::make_heap)。
std::vector<int> scores{4, 1, 7, 3, 9, 2};
std::make_heap(scores.begin(), scores.end()); // 可能结果之一:9 4 7 3 1 2
靠近叶子的节点数量多但可下沉高度低,累计下沉成本呈线性级别,因此已有全量数据时应批量建堆而非逐个插入:
| 建堆方式 | 调整方向 | 比较次数上界(N = distance(first, last)) | 适用场景 |
|---|---|---|---|
批量 make_heap | 从 (n - 2) / 2 自底向上下沉 | 至多 3N 次(O(N)) | 已有完整集合,一次性建堆 |
逐个 push_heap | 逐元素沿父链上浮 | O(N log N) | 数据流式到达且需持续维护堆顶 |
边界与误区
- 输出排列不唯一:标准只约束堆不变量与复杂度上界,不同实现可产出不同数组排列;测试应检查根与父子关系,不能硬编码单一序列。
- 比较器须全程一致:
std::less<>建出的堆,后续push_heap、pop_heap、sort_heap、is_heap与is_heap_until必须沿用同一比较器,中途换用std::greater<>会直接破坏合法性。
31.3 push_heap
std::push_heap 要求 [first, last - 1) 已是合法堆且新元素位于 last - 1。它让最右叶子处的新元素沿父链上浮,直到到达根节点或父子关系合法,从而使 [first, last) 恢复堆序。
这里体现清晰的职责分层:push_back 负责容器层元素构造、扩容、迭代器失效与异常安全,push_heap 仅负责算法层父子顺序修复。
std::vector<int> heap{9, 5, 7, 1, 3, 4, 6};
heap.push_back(8); // 容器层:追加到索引 7
// 算法层上浮:8 > 父(3)=1 -> 上浮;8 > 父(1)=5 -> 上浮;8 <= 父(0)=9 -> 停止
std::push_heap(heap.begin(), heap.end()); // 一种结果:9 8 7 5 3 4 6 1
新元素仅沿单条父链移动,标准比较次数上界为 log(N)(N = distance(first, last));若元素移动代价高,还应计入对象移动与交换成本。
边界与误区
push_heap 只修复尾元素引起的局部破坏,不会全局重建已损坏的 [first, last - 1)。前缀来源不可信时,应先用 is_heap 或 is_heap_until 检查,再决定调用 make_heap 重建还是直接增量入堆。
31.4 pop_heap
std::pop_heap 将堆顶与 last - 1 交换,再把旧尾元素沿较高优先级孩子下沉,以修复 [first, last - 1)(标准比较次数上界为 2 log(N))。
尽管带 pop 字样,pop_heap 不会缩短容器;完整出堆须按“算法重排 → 读取尾部 → 容器删尾”三步执行,保持算法层与容器层解耦及异常安全边界清晰:
std::vector<int> heap{9, 8, 7, 5, 3, 4, 6, 1};
if (!heap.empty()) {
std::pop_heap(heap.begin(), heap.end()); // 1. 交换根与尾并修复前缀
int highest = heap.back(); // 2. 读取原堆顶(9)
heap.pop_back(); // 3. 容器层缩短序列
}
// 剩余合法堆前缀:8 5 7 1 3 4 6
边界与误区
- 非空合法前提:
pop_heap要求[first, last)为非空合法堆;空区间无可交换元素,损坏的堆无法保证尾部得到全局最高优先级元素。 - 判空不防篡改:
!heap.empty()只守住空区间边界;若上游可能直接改写底层数组,需配合is_heap断言,或改用受限封装std::priority_queue。
31.5 sort_heap
std::sort_heap 将合法堆原地转为有序序列,标准比较次数上界为 2N log N(O(N log N),参见 std::sort_heap):默认 std::less 最大堆得到升序,std::greater 最小堆得到降序。
std::vector<int> heap{4, 1, 7, 3, 9, 2};
std::make_heap(heap.begin(), heap.end());
std::sort_heap(heap.begin(), heap.end()); // 默认比较器下得到升序:1 2 3 4 7 9
状态演进等价于循环弹出堆顶并收缩有效堆前缀——前缀保持堆序,尾部逐步积累已排序后缀:
template<class RandomIt>
void teaching_sort_heap(RandomIt first, RandomIt last)
{
while (first != last) {
std::pop_heap(first, last);
--last;
}
}
边界与误区
sort_heap 会消耗堆不变量:排序完成后整段不再是堆,不能继续调用 push_heap 或 pop_heap。若后续仍需优先级队列操作,必须在排序前拷贝数据,或事后重新调用 make_heap。
31.6 is_heap
std::is_heap 线性扫描每个非根节点 i 与父节点 (i - 1) / 2,判断整段区间是否满足堆不变量并返回 bool;不修改元素也不分配内存。
std::vector<int> heap{9, 5, 7, 1, 3, 4, 6};
std::vector<int> broken{9, 5, 7, 8, 3, 4, 6};
bool a = std::is_heap(heap.begin(), heap.end()); // true
bool b = std::is_heap(broken.begin(), broken.end()); // false
is_heap 与 make_heap 分别承担“验证契约”和“接管状态”两种角色:
| 算法 | 作用与副作用 | 复杂度 | 工程定位 |
|---|---|---|---|
std::is_heap | 只读校验整段是否成堆,返回 bool | O(N) | 调试断言、单元测试与可信输入边界校验 |
std::make_heap | 原地重排以建立堆不变量 | O(N)(≤ 3N 次比较) | 输入来源不可信或初次批量建堆 |
关键事实
- 避开热路径:
is_heap需线性遍历区间,适合放在边界断言中,不应在每次堆操作后常规调用。 - 并发重载:C++17 起提供 execution policy 重载;常规前置校验用顺序版本即可,启用并行前需核对库实现、数据规模与异常策略。
31.7 is_heap_until
std::is_heap_until 返回首个破坏堆序的迭代器 i,使 [first, i) 为最大合法堆前缀,且满足 i == last 或 *i 破坏父子关系;std::is_heap(first, last) 等价于 std::is_heap_until(first, last) == last。
std::vector<int> data{9, 5, 7, 1, 3, 4, 6};
data.push_back(8);
// 索引 7 的父节点索引 3 值为 1,1 >= 8 不成立
auto first_bad = std::is_heap_until(data.begin(), data.end());
std::ptrdiff_t index = first_bad - data.begin(); // 7
简化实现展示了线性扫描顺序(标准库另有投影、ranges 与执行策略重载):
template<class RandomIt, class Compare>
RandomIt teaching_is_heap_until(RandomIt first, RandomIt last, Compare comp)
{
auto n = last - first;
for (decltype(n) child = 1; child < n; ++child) {
auto parent = (child - 1) / 2;
if (comp(*(first + parent), *(first + child))) {
return first + child;
}
}
return last;
}
核心判断
is_heap_until 返回按数组下标线性扫描最先失败的位置,未必是数值差最大或树深最深的错误点。在单测与排错中,它能把“堆被破坏”精确定位到具体下标(如 push_back 后漏调 push_heap 的末尾位置)。
31.8 priority_queue 与 heap algorithm 的关系
std::priority_queue 默认为 std::priority_queue<T, std::vector<T>, std::less<T>>,把底层容器与比较器封装为受保护成员,通过受限接口自动维持堆序(详见 std::priority_queue):
top():O(1)读取堆顶。push/emplace:尾部追加后调用push_heap(O(log N))。pop:调用pop_heap后再pop_back()删尾(O(log N))。
所有 <algorithm> 堆算法均不改变容器大小,其调用契约如下:
| 算法 | 前置条件 | 比较次数上界 | 调用后区间状态 |
|---|---|---|---|
make_heap | 随机访问区间 [first, last) | 3N | 整段成堆 |
push_heap | [first, last - 1) 已成堆 | log(N) | [first, last) 成堆 |
pop_heap | [first, last) 为非空堆 | 2 log(N) | [first, last - 1) 成堆,原堆顶在 last - 1 |
sort_heap | [first, last) 已成堆 | 2N log N | 整段有序,消耗堆不变量 |
is_heap | 随机访问区间 [first, last) | 最多 N - 1 | 返回是否成堆(只读) |
is_heap_until | 随机访问区间 [first, last) | 最多 N - 1 | 返回最大堆前缀结束位置(只读) |
选择封装适配器还是裸堆算法,取决于调用方是否需要控制底层存储与诊断状态:
| 选型维度 | std::priority_queue | 手写 STL 堆算法(<algorithm>) |
|---|---|---|
| 边界管理 | 自动绑定 push_back / pop_back | 调用方自行维护容器大小与区间边界 |
| 接口权限 | 受限(不可遍历、不可任意删改) | 完全开放(支持切片、sort_heap、is_heap_until) |
| 不变量保护 | 强封装,外部无法破坏内部堆序 | 依赖调用纪律,外部改写即损坏堆序 |
| 典型场景 | 任务调度、Top-K 候选集、图算法 Frontier | 批量建堆转排序、复用 vector、算法组合与调试 |
比较器方向在两者中一致:Compare 定义严格弱序中“排在前面”的关系,堆顶输出排在最后的元素(默认 std::less<int> 为最大堆,std::greater<int> 为最小堆):
std::priority_queue<int> max_ready;
max_ready.push(4);
max_ready.push(9);
max_ready.push(7);
int max_top = max_ready.top(); // 9
max_ready.pop(); // 移除 9,新 top 为 7
std::priority_queue<int, std::vector<int>, std::greater<int>> min_ready;
min_ready.push(4);
min_ready.push(9);
min_ready.push(7);
int min_top = min_ready.top(); // 4
排查顺序
- 形态选型:仅需优先级出队选
std::priority_queue,需原地排序、复用vector或诊断破坏点选裸堆算法。 - 迭代器能力:确认底层支持随机访问(
std::vector/std::deque可用,std::list不可用)。 - 比较器一致:所有操作沿用同一比较器,明确
std::less(最大堆)与std::greater(最小堆)方向。 - 调用前提:核对
push_heap前旧前缀成堆、pop_heap前非空、sort_heap前整段合法。 - 成本与失效:评估元素移动开销及
vector扩容造成的迭代器/引用失效。
最小自检任务
阅读下面代码,判断各步区间状态并回答:
is_heap_until在追加8后返回哪个位置?push_heap后可能得到什么数组?pop_heap后尾部元素是什么?- 为什么
pop_heap后还需要pop_back?
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> heap{9, 5, 7, 1, 3, 4, 6};
heap.push_back(8);
auto broken = std::is_heap_until(heap.begin(), heap.end());
std::push_heap(heap.begin(), heap.end());
std::pop_heap(heap.begin(), heap.end());
int moved_top = heap.back();
heap.pop_back();
}
本章知识点总结
- 堆不变量与索引
堆在随机访问区间上模拟完全二叉树,父节点为
(i - 1) / 2、左右孩子为2 * i + 1与2 * i + 2,且满足comp(parent, child) == false(std::list不可用)。 - 比较器方向与一致性
默认
std::less为最大堆、std::greater为最小堆;建堆、入堆、出堆、排序与检查须全程使用同一比较器。 - 建堆与入堆分工
make_heap自底向上原地建堆(至多3N次比较);push_heap假定[first, last - 1)已成堆,只上浮尾元素(上界log(N)次比较)。 - 出堆与删尾分离
pop_heap把堆顶换至末尾并修复[first, last - 1)(上界2 log(N)次比较),但不缩短容器,须紧接pop_back()删除。 - 堆排序消耗不变量
sort_heap反复弹出堆顶使区间有序(上界2N log N次比较),完成后原堆序被消耗,不可再直接push_heap/pop_heap。 - 校验与排错分工
is_heap线性判真假,适合断言而非热路径;is_heap_until按数组下标顺序返回首个破坏点,适合定位漏调push_heap等故障。 - 适配器选型边界
仅需优先级出队选
std::priority_queue;需原地排序、复用vector或诊断破坏点选裸堆算法,按“选型 → 迭代器 → 比较器 → 前提 → 成本”排查。