Skip to main content

Chapter 31: Heap Algorithms

核心问题与阅读主线

本章导读8 个核心小节 · 附自检与总结

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只读校验整段是否成堆,返回 boolO(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

排查顺序

  1. 形态选型:仅需优先级出队选 std::priority_queue,需原地排序、复用 vector 或诊断破坏点选裸堆算法。
  2. 迭代器能力:确认底层支持随机访问(std::vector / std::deque 可用,std::list 不可用)。
  3. 比较器一致:所有操作沿用同一比较器,明确 std::less(最大堆)与 std::greater(最小堆)方向。
  4. 调用前提:核对 push_heap 前旧前缀成堆、pop_heap 前非空、sort_heap 前整段合法。
  5. 成本与失效:评估元素移动开销及 vector 扩容造成的迭代器/引用失效。

最小自检任务​

动手自检先独立判断

阅读下面代码,判断各步区间状态并回答:

  1. is_heap_until 在追加 8 后返回哪个位置?
  2. push_heap 后可能得到什么数组?
  3. pop_heap 后尾部元素是什么?
  4. 为什么 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 或诊断破坏点选裸堆算法,按“选型 → 迭代器 → 比较器 → 前提 → 成本”排查。