Chapter 31: Heap Algorithms

Heap algorithm 处理的对象是一段随机访问区间上的堆不变量。读完本章后，读者应能把 std::make_heap、std::push_heap、std::pop_heap、std::sort_heap、std::is_heap 和 std::is_heap_until 放回同一条状态路径中，判断调用前提、比较器方向、有效堆区间和尾部元素的关系。

本章的主线材料是一段 std::vector<int>。这段 vector 同时承担底层连续存储、随机访问索引、堆区间边界和 std::priority_queue 默认底层容器的角色。heap algorithm 自身只重排 [first, last) 中已经存在的元素；元素的插入、删除、容量变化和生命周期仍由容器完成。

C++ 标准草案的 heap operations 把堆定义在随机访问范围上：对任意子节点索引 i，父节点索引是 (i - 1) / 2，并且 comp(parent, child) 为 false。在默认 std::less 关系下，父节点小于子节点时会破坏堆序，所以堆顶保存最大元素。

下面的代码贯穿本章。它展示了普通区间如何变成堆，新元素如何进入堆，堆顶如何被移到尾部，检查算法如何定位破坏位置，以及堆最终如何被消耗成有序区间。

#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 让 vector 增加一个真实元素，push_heap 只把最后一个位置纳入堆；pop_heap 只把堆顶交换到尾部，pop_back 才真正缩短容器；sort_heap 之后整段区间变成有序序列，原来的堆不变量被排序结果替代。

堆算法的状态路径可以压缩成下面这张图。图中的“堆区间”始终是 [first, last) 或者被操作缩短后的前缀，尾部元素在 pop_heap 和 sort_heap 中承担临时结果区。

31.1 heap 数据结构

Heap 在 STL algorithm 语境中是一段连续逻辑数组上的完全二叉树。连续逻辑数组通常来自 std::vector 或 std::deque，算法通过随机访问迭代器使用下标关系，不要求节点对象保存 parent、left 或 right 指针。

索引关系决定了堆算法的最小信息集。位置 0 是根节点，位置 i 的左孩子是 2 * i + 1，右孩子是 2 * i + 2，父节点是 (i - 1) / 2。只要迭代器支持 first + n、last - first 和下标式移动，算法就能在区间上模拟树结构。

默认最大堆的判断规则是：每个父节点都按照比较器排在它的孩子之后。用 std::less<int> 时，comp(parent, child) 等价于 parent < child，该表达式必须为 false，所以父节点值大于或等于孩子值。把比较器换成 std::greater<int> 后，堆顶会变成最小值，因为此时 parent > child 必须为 false。

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());

这个例子说明了 heap algorithm 的第一个边界：堆只保证根节点是当前最高优先级元素，同时保证父子局部顺序。兄弟节点之间、同一层节点之间、不同子树之间没有全局排序承诺。{9, 5, 7, 1, 3, 4, 6} 是合法最大堆，但整体顺序既不满足升序，也不满足降序。

堆算法依赖随机访问迭代器，因为父子位置需要常数时间跳转。std::list 这类双向链表即使可以逐个元素比较，也无法用 first + child_index 定位孩子，因而不适合作为这些算法的输入区间。这个约束解释了 std::priority_queue 的默认底层容器选 std::vector，可替换容器也需要满足随机访问和尾部插删接口。

31.2 make_heap

std::make_heap 把普通随机访问区间原地重排成堆。它的输入是一段已经存在的元素，输出是同一段存储上的合法堆区间；它不分配新节点，也不改变容器大小。

常见实现形状是自底向上调整。算法从最后一个非叶子节点开始，把每个子树修复成局部堆，然后一路向前处理到根节点。叶子节点天然满足堆不变量，所以起点通常是 (n - 2) / 2。每次调整时，当前值沿着较高优先级孩子方向下沉，直到父子关系重新满足比较器。

std::vector<int> scores{4, 1, 7, 3, 9, 2};
std::make_heap(scores.begin(), scores.end());

// 可能结果之一：9 4 7 3 1 2
// 具体排列允许存在实现差异；根节点和父子关系才是语义重点。

这个示例说明 make_heap 的结果具有多解。标准约束的是堆不变量和复杂度上界，不要求所有实现产出同一个数组排列。读源码或调试输出时，应该检查每个父子关系和堆顶元素，而非把某一次输出当成唯一形状。

自底向上的构造解释了 make_heap 的线性复杂度。虽然一次下沉最多走树高 O(log N)，但靠近叶子的节点数量更多、可下沉高度更低。所有节点的下沉成本累计后落在线性级别。标准对经典算法给出至多 3N 次比较的上界，std::make_heap 的文档也按 N = distance(first, last) 表达这个复杂度承诺。

make_heap 的工程用途是批量建堆。已有一批元素时，先放进 vector 再调用 make_heap，通常比逐个 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) 成为新堆。

std::vector<int> heap{9, 5, 7, 1, 3, 4, 6};
heap.push_back(8);                         // 先让容器拥有新元素
std::push_heap(heap.begin(), heap.end());   // 再把最后一个元素上浮进堆

// 一种结果：9 8 7 5 3 4 6 1

这段代码中，push_back 和 push_heap 分别负责两个层级。push_back 负责容器层面的元素构造、容量增长、迭代器失效和异常安全；push_heap 负责算法层面的父子顺序修复。把二者混在一起理解，会误判 push_heap 的能力边界。

常见实现形状是上浮。新元素先位于数组尾部，对应完全二叉树的最右叶子。算法比较它和父节点。如果新元素优先级更高，就把父节点下移，新元素继续沿父链向上。到达根节点或父子关系合法时，上浮停止。

std::vector<int> heap{9, 5, 7, 1, 3, 4, 6, 8};

// 新元素 8 在索引 7，父节点索引 3，值为 1。
// 8 比 1 优先级高，继续和索引 1 的 5 比较。
// 8 比 5 优先级高，继续和索引 0 的 9 比较。
// 9 仍保持根节点，最终得到 9 8 7 5 3 4 6 1。
std::push_heap(heap.begin(), heap.end());

push_heap 的比较次数是对数级，因为新元素只沿一条父链移动。标准语义给出的上界是 log(N) 次比较，其中 N 是调用时区间长度。真实运行中还会有元素移动或交换成本；当元素类型移动昂贵时，比较次数之外的对象移动也会进入性能判断。

调用前提是本节最容易出错的点。push_heap 只修复最后一个元素造成的局部破坏。若 [first, last - 1) 早已破坏堆序，push_heap 没有全局重建义务。工程代码中发现堆来源不确定时，应先用 is_heap 或 is_heap_until 验证，再选择 make_heap 重建或执行增量插入。

31.4 pop_heap

std::pop_heap 把堆顶元素交换到尾部，并把前缀 [first, last - 1) 重新修复成堆。它的名字包含 pop，但它不会缩短容器；真正删除尾部元素需要由调用方继续执行 pop_back 或等价操作。

std::vector<int> heap{9, 8, 7, 5, 3, 4, 6, 1};

std::pop_heap(heap.begin(), heap.end());
int highest = heap.back();
heap.pop_back();

// highest == 9
// 剩余前缀重新成为合法堆：8 5 7 1 3 4 6

这段代码把堆顶读取分成三步。第一步 pop_heap 把最高优先级元素移到尾部；第二步从 back() 读取它；第三步用容器操作缩短元素序列。这个顺序让算法层和容器层保持分离，也让异常安全责任更清楚。

常见实现形状是交换根和尾，再下沉新根。根位置得到原尾部元素后，算法在两个孩子中选择优先级更高者，把它上移到父位置，原尾部元素继续向下寻找合适位置。这个过程沿一条从根到叶子的路径推进，所以比较次数是对数级，标准上界是 2 log(N) 次比较。

pop_heap 的输入区间必须是非空合法堆。空区间没有根节点和尾部元素可交换；破坏堆序的区间无法保证尾部得到全局最高优先级元素。调用前可以用 empty() 处理容器边界，用 is_heap 处理调试断言。

std::vector<int> heap{9, 8, 7, 5, 3, 4, 6, 1};

if (!heap.empty()) {
    std::pop_heap(heap.begin(), heap.end());
    heap.pop_back();
}

这个保护只解决空区间问题。若上游代码可能直接改写底层数组，仍需要验证堆不变量。std::priority_queue 把底层容器封装起来，正是为了让外部代码通过受限接口维护这个不变量。

31.5 sort_heap

std::sort_heap 把一个合法堆区间转换成有序区间。默认 std::less 下，最大堆经过 sort_heap 后得到升序结果；使用 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

sort_heap 的常见实现可以理解为反复调用 pop_heap。每次 pop_heap 把当前堆顶放到有效堆区间的最后一个位置，然后把有效堆区间缩短一位。尾部区域逐步积累已确定位置的元素，前缀继续保持堆。

template<class RandomIt>
void teaching_sort_heap(RandomIt first, RandomIt last)
{
    while (first != last) {
        std::pop_heap(first, last);
        --last;
    }
}

这段教学代码展示的是算法形状。标准库实现可以使用更细致的内部辅助函数，但核心状态仍是“前缀为堆，尾部为已排序结果”。std::sort_heap 的可能实现也以循环调用 pop_heap 的形式表达这一点。

sort_heap 会消耗堆不变量。排序完成后，整个区间满足有序关系，但不再作为堆继续服务 push_heap 或 pop_heap 的前提。若后续还要做优先级队列操作，需要重新 make_heap，或者在排序前复制一份数据用于输出。

复杂度来自反复弹出堆顶。每次弹出是 O(log N) 量级，重复 N 次得到 O(N log N)。标准上界以 2N log N 次比较描述。这个复杂度模型说明 sort_heap 是堆排序形态，适合在已经持有堆的区间上完成原地排序。

31.6 is_heap

std::is_heap 检查整段区间是否满足堆不变量。它返回 bool，适合放在断言、调试检查、测试用例和算法分支中，用来确认后续 push_heap、pop_heap 或 sort_heap 的调用前提。

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

检查过程可以按数组父子关系线性扫描。对每个非根节点 i，算法比较父节点 (i - 1) / 2 和当前节点 i。默认最大堆下，如果 parent < child，区间在 i 处破坏堆序。扫描完成且没有发现破坏点时，结果为 true。

is_heap 的复杂度是线性级，因为每个子节点最多参与一次父子检查。它不会改变元素顺序，也不会分配存储。对调试代码而言，这个成本通常可以接受；对热路径而言，应把它作为边界验证工具，而非每次堆操作后的常规运行成本。

C++17 起，部分检查算法存在 execution policy 重载。堆检查虽然可以从父子关系集合上看成多点检查，但工程代码仍应先确认标准库实现、数据规模和异常策略是否匹配。对普通业务代码，顺序版本已经能表达清楚的前置条件验证。

is_heap 和 make_heap 的角色不同。is_heap 给出判断结果，make_heap 负责修复或构造。输入来源可信时，is_heap 可以作为断言；输入来源不稳定时，make_heap 可以直接建立新的堆状态。选择哪一个，取决于你要验证契约还是要接管数据状态。

31.7 is_heap_until

std::is_heap_until 返回第一个让堆前缀停止成立的位置。更精确地说，它返回某个迭代器 i，使 [first, i) 是堆，并且 i == last 或 *i 所在位置破坏了父子关系。std::is_heap 可以理解为 is_heap_until(first, last) == last。

std::vector<int> data{9, 5, 7, 1, 3, 4, 6};
data.push_back(8);

// data 现在是 9 5 7 1 3 4 6 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

这个返回值比 is_heap 更适合排查。它告诉你最大合法前缀在哪里结束，也能直接定位到第一处父子关系破坏点。调试增量插入时，如果 push_back 后忘记调用 push_heap，is_heap_until 往往会指向刚追加的尾部位置。

is_heap_until 的线性扫描顺序也解释了“第一处破坏”的含义。它按照数组顺序检查子节点，返回最先使父子关系失败的迭代器。这个位置不一定是数值差异最大的节点，也不一定是所有错误中最深的节点；它是标准扫描顺序下能证明堆前缀停止成立的位置。

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;
}

这段教学代码只展示默认迭代器形状和比较器检查。真实标准库还要处理重载、投影、ranges 接口和执行策略，但核心判断仍是父子关系。把 is_heap_until 放进单元测试中，可以把“堆被破坏”从一个笼统的失败变成可定位的数组位置。

31.8 priority_queue 与 heap algorithm 的关系

std::priority_queue 是容器适配器，它把底层容器、比较器和 heap algorithm 组合成受限接口。默认模板形态是 std::priority_queue<T, std::vector<T>, std::less<T>>；底层容器通常保存为受保护成员，比较器也作为状态保存。用户通过 push、emplace、pop 和 top 操作优先级队列，底层堆区间由适配器维护。

priority_queue 的接口目标是维护不变量。top() 常数时间返回最高优先级元素；push 和 emplace 先把元素放到底层容器尾部，再执行类似 push_heap 的修复；pop 执行类似 pop_heap 的堆顶转移，再缩短底层容器。cppreference 对 std::priority_queue 的描述也强调了常数时间访问最大元素、对数级插入和提取。

std::priority_queue<int> ready;
ready.push(4);
ready.push(9);
ready.push(7);

int current = ready.top(); // 9
ready.pop();              // 9 被移除，新的 top 是 7

这段代码隐藏了底层堆数组。调用者只看到优先级队列语义，不需要关心 pop_heap 后尾部元素何时删除，也无法拿到迭代器去破坏内部顺序。这种封装减少了误用空间，代价是接口能力受限：不能遍历内部元素，不能删除任意位置，不能直接修改某个元素后通知堆修复。

手写 heap algorithm 适合底层区间需要被复用、排序、调试或和其他算法组合的场景。比如已有 vector 既要批量 make_heap，又要用 sort_heap 输出有序结果；或者需要用 is_heap_until 定位上游改写造成的破坏。priority_queue 适合表达长期维护的优先级抽象，尤其适合任务调度、Top-K 候选集和图算法中的待处理集合。

比较器方向在 priority_queue 中同样遵循堆算法规则。Compare 表示弱序中“排在前面”的关系，但队列输出的是该弱序中靠后的元素。默认 std::less<int> 让较大的整数成为 top()；std::greater<int> 让较小的整数成为 top()。

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 current = min_ready.top(); // 4

迁移到工程代码时，可以按固定顺序判断：先确认你需要的是裸区间算法还是受限优先级队列；再确认底层区间是否支持随机访问；再确认比较器是否在所有操作中一致；接着检查调用前提，如 push_heap 前的旧前缀、pop_heap 前的非空堆、sort_heap 前的合法堆；最后再评估复杂度、元素移动成本和容器扩容造成的迭代器失效。

最小自检任务

给定下面这段代码，判断每一步之后区间状态。要求回答四个问题：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();
}

答案要点

heap.push_back(8) 后，数组为 {9, 5, 7, 1, 3, 4, 6, 8}。索引 7 的父节点是索引 3，值为 1，默认最大堆下父节点需要大于或等于孩子节点，所以 is_heap_until 返回 heap.begin() + 7。

std::push_heap 只修复最后一个元素造成的破坏。8 会先和 1 交换，再和 5 交换，最终可能得到 {9, 8, 7, 5, 3, 4, 6, 1}。根节点 9 仍然保持最高优先级。

std::pop_heap 把根节点 9 交换到尾部，并把前缀重新修复成堆，所以 moved_top == 9。此时容器大小仍然没有改变，尾部保存的是刚移出的顶值，前缀 [begin, end - 1) 才是继续可用的堆区间。

pop_heap 后需要 pop_back，因为删除元素属于容器层责任。算法只负责重排区间，不负责缩短 vector、析构尾部元素或更新容器大小。这个分层也是 priority_queue::pop 封装底层堆算法的原因。

本章知识点总结

• 堆不变量：heap algorithm 在随机访问区间上维护父子局部顺序，默认 std::less 下根节点保存最大元素。
• 数组索引：堆用连续逻辑数组表达完全二叉树，父子位置由 (i - 1) / 2、2 * i + 1 和 2 * i + 2 决定。
• 随机访问：堆算法需要常数时间下标跳转，因此输入迭代器必须支持随机访问能力。
• 比较器方向：comp(parent, child) 为 false 是父子合法条件，换比较器会改变堆顶语义。
• make_heap：make_heap 把已有区间原地构造成堆，常见实现从最后一个非叶子节点向根节点下沉调整。
• push_heap：push_heap 要求旧前缀已经是堆，并只把尾部新元素沿父链上浮到合法位置。
• pop_heap：pop_heap 把堆顶移到尾部并修复前缀，删除尾部元素仍由容器操作完成。
• sort_heap：sort_heap 反复弹出堆顶，把堆区间消耗成有序区间，排序完成后原堆不变量被消耗。
• is_heap：is_heap 线性检查整段区间是否满足堆不变量，适合作为断言和前置条件验证。
• is_heap_until：is_heap_until 返回堆前缀停止成立的位置，适合定位第一处父子关系破坏点。
• priority_queue：priority_queue 用受限接口封装底层容器和堆算法，提供常数时间 top 与对数级插入、提取。
• 判断顺序：工程使用时先选裸区间或适配器，再查随机访问能力、比较器一致性、调用前提、复杂度和容器失效边界。