Chapter 24: Priority Queue

std::priority_queue 解决的问题很具体：调用方持续加入元素，每次只关心“当前优先级最高的那个元素”。它把“按优先级取下一个”做成稳定接口，同时把底层的数组、堆调整和比较器方向封装起来。

这一章的主线是一组待执行任务：每个任务有 priority、sequence 和 name。我们希望优先级大的任务先执行；优先级相同时，sequence 小的任务先执行。读完本章后，读者应能定位 priority_queue 的状态来源，判断 top 的语义，追踪 push、pop 如何维护堆不变量，并在 priority_queue 与 set 之间做工程选型。

标准层面，std::priority_queue 是容器适配器（container adaptor）。它通常持有一个底层容器 c 和一个比较器 comp；成员操作的效果可以理解为在底层容器上调用 push_back、pop_back、front，再配合 make_heap、push_heap、pop_heap 维护堆结构。C++ working draft 的 priority_queue 条目也用这种 exposition 形式描述成员效果。

贯穿本章的最小材料如下。这个比较器的方向是全章最容易判断错的位置。

#include <queue>
#include <string>
#include <vector>

struct Task {
    int priority;
    int sequence;
    std::string name;
};

struct TaskOrder {
    bool operator()(const Task& lhs, const Task& rhs) const {
        if (lhs.priority != rhs.priority) {
            return lhs.priority < rhs.priority;
        }
        return lhs.sequence > rhs.sequence;
    }
};

using ReadyQueue = std::priority_queue<Task, std::vector<Task>, TaskOrder>;

TaskOrder 返回 true 表示 lhs 在弱序关系中排在 rhs 前面。std::priority_queue 的 top 返回这个弱序关系下排在最后的元素，所以 priority 最大的任务会浮到堆顶；同优先级时，sequence 更小的任务会浮到堆顶。

24.1 heap-backed adaptor model

heap-backed adaptor model 的核心判断是：priority_queue 的接口表现为队列，内部形状是随机访问区间上的二叉堆。队列接口只暴露 push、pop、top、empty、size 等操作；堆结构则通过数组下标表达父子关系，并通过比较器维持根节点的优先级。

二叉堆（binary heap）在数组中使用下标关系表达树形结构。对位置 i 来说，父节点位置是 (i - 1) / 2，左孩子是 2 * i + 1，右孩子是 2 * i + 2。这组关系要求底层区间支持随机访问，所以 heap 算法要求 random access iterator。

堆不变量可以写成一个检查式：对任意非根位置 i，comp(parent, child) 应为 false。在默认 std::less<T> 下，comp(parent, child) 等价于 parent < child，所以父节点不会小于孩子节点，根节点就是当前最大元素。换成 std::greater<T> 后，父节点不会大于孩子节点，根节点就是当前最小元素。

priority_queue 把这个堆区间封装成适配器。标准描述中的受保护成员 c 表示底层容器，comp 表示比较器；top() 的效果是读取 c.front()，push() 的效果是先把元素追加到 c 末尾，再把新元素上浮到合法位置，pop() 的效果是先把堆顶元素调整到末尾，再从底层容器移除末尾元素。

接口层动作	底层状态动作	堆不变量结果
top()	读取 c.front()	不改变堆
push(x)	c.push_back(x) 后调用 push_heap	新元素进入堆
emplace(args...)	c.emplace_back(args...) 后调用 push_heap	新对象进入堆
pop()	调用 pop_heap 后 c.pop_back()	原堆顶被移除
构造自区间	初始化 c 后调用 make_heap	整个区间成为堆

从源码阅读角度看，priority_queue 的关键不在成员函数数量，而在“适配器接口 + 底层容器 + heap 算法”三者的组合。阅读常见实现时，应先找到类模板参数 T、Container、Compare，再找 c、comp 两个成员，最后把 push、pop、构造函数映射到 push_heap、pop_heap、make_heap。

这个模型带来一个直接工程后果：priority_queue 只承诺快速访问当前最高优先级元素。它不提供迭代器，不提供按键查找，也不提供删除任意元素的接口。调用方只能通过持续 top 和 pop 消费元素，或者另外维护索引结构记录元素身份。

回到 Task 示例，ReadyQueue 的堆顶永远是当前应执行的任务。队列内部可以有多个同优先级任务，也可以出现数组顺序看起来不完全排序的状态；只要根节点符合比较器定义下的最高优先级，且每个父子关系满足堆不变量，priority_queue 的接口语义就是成立的。

24.2 vector 底层容器与 comparator

默认底层容器是 std::vector<T>，因为堆调整需要用下标快速访问父节点和孩子节点。std::vector 的连续存储让 (i - 1) / 2、2 * i + 1 这类位置计算可以直接转成随机访问迭代器移动，常数开销小，缓存局部性也通常优于节点式结构。

priority_queue 对底层容器的要求来自 heap 算法和适配器接口。容器需要提供随机访问迭代器，还需要提供 front()、push_back() 和 pop_back()。因此 std::vector<T> 和 std::deque<T> 是常见选择；std::list<T> 缺少随机访问能力，无法作为标准 priority_queue 的底层容器。

比较器 Compare 决定优先级方向。它的语义来自严格弱序（strict weak ordering）：comp(a, b) 返回 true 表示 a 在排序关系中位于 b 之前。priority_queue 输出的是这个关系中位于最后的元素，所以默认 std::less<T> 形成最大堆，std::greater<T> 形成最小堆。

下面的代码展示三种比较器方向。它们使用同一批输入数据，但 top() 的含义不同。

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_heap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    for (int value : {4, 1, 7, 3}) {
        max_heap.push(value);
        min_heap.push(value);
    }

    std::cout << max_heap.top() << '\n'; // 7
    std::cout << min_heap.top() << '\n'; // 1
}

std::greater<int> 没有改变底层容器形状，也没有把 priority_queue 变成有序数组。它只是改变父子关系的比较方向，使堆顶成为当前最小值。调用方判断比较器时，应把问题翻译成一句话：comp(a, b) 为 true 时，a 会排在 b 前面，top 会返回排在最后的元素。

TaskOrder 示例也按同一条规则工作。priority 小的任务排在 priority 大的任务前面，所以 priority 大的任务成为堆顶；同优先级时，sequence 大的任务排在 sequence 小的任务前面，所以 sequence 小的任务成为堆顶。这种写法把“同优先级按进入顺序执行”的稳定需求显式编码进元素，调用方不依赖容器自动记住插入顺序。

ReadyQueue ready;
ready.push(Task{5, 0, "parse"});
ready.push(Task{9, 1, "render"});
ready.push(Task{5, 2, "write"});

const Task& next = ready.top(); // render

比较器可以有状态，但有状态比较器会增加维护成本。队列构造后，所有堆调整都依赖同一个 comp 状态；如果比较器读取外部可变对象，例如全局优先级表，外部状态变化不会自动触发重新建堆。稳定做法是把参与比较的关键字段放进元素，或者在优先级变化时重新插入元素、重建堆，或改用支持定位和更新的结构。

比较器还应保持无副作用。heap 算法会多次调用比较器，并且调用次数与堆高度相关；比较器修改元素、记录不稳定状态或依赖时间变化，会让同一组元素在不同调用中得到不同关系，从而破坏严格弱序。工程代码中，比较器应被当成纯判断函数：输入两个元素，返回固定的先后关系。

24.3 push、pop 与 top 的堆状态路径

push 的状态路径分成两个阶段：先把新元素放到数组末尾，再沿父节点方向上浮。追加阶段由底层容器负责内存和对象构造；上浮阶段由 push_heap 负责比较和移动元素。对于默认 std::vector，追加可能触发扩容，扩容会移动或拷贝已有元素，并使旧引用、指针和迭代器失效。

下面的队列在三次 push 后，top 会返回 render。数组内部顺序由堆调整决定，调用方不应从内部顺序推导完整排序。

ReadyQueue ready;
ready.push(Task{5, 0, "parse"});
ready.push(Task{9, 1, "render"});
ready.push(Task{5, 2, "write"});

std::cout << ready.top().name << '\n'; // render

第一次插入后，堆只有一个元素。第二次插入 render 后，新元素先进入末尾；push_heap 比较父节点 parse 和新元素 render，TaskOrder(parse, render) 为 true，表示 parse 排在 render 前面，于是 render 上浮到根节点。第三次插入 write 后，它与父节点比较，发现优先级低于根节点，最终留在下层位置。

top 只读取根节点。它通常是常数时间操作，返回的是 const_reference，所以调用方可以读取堆顶元素，但不能通过该引用修改堆顶关键字段。这个限制服务堆不变量：如果调用方能直接修改 priority，底层数组上的父子关系就可能立即失效。

pop 的状态路径也分成两个阶段：先把堆顶元素移到末尾并修复剩余区间，再移除末尾元素。pop_heap 只调整区间，不缩短容器；priority_queue::pop 会在 pop_heap 之后调用底层容器的 pop_back()。因此 pop() 只删除当前堆顶，不返回被删除元素。

读取并删除堆顶时，应先复制或移动需要的值，再调用 pop()。下面的写法把被执行任务保存到局部对象，随后队列可以安全进入下一个状态。

while (!ready.empty()) {
    Task task = ready.top();
    ready.pop();
    std::cout << task.name << '\n';
}

这个代码片段有两个工程细节。第一，top() 返回引用，pop() 后引用指向的对象状态已经不适合继续使用，所以需要先把值保存出来。第二，pop() 可能移动底层数组中的多个元素，读取下一个任务必须重新调用 top()。

异常安全边界需要按阶段判断。底层 vector::push_back 可能因为分配或元素构造失败而抛出；比较器、元素移动或赋值也可能在 heap 调整期间抛出。工程上应把比较器设计成廉价且不抛异常的纯函数，并让元素的移动操作保持可预测成本。阅读标准库实现时，检查点是追加完成前后的提交位置、heap 调整失败后的容器状态承诺，以及比较器调用是否可能传播异常。

迭代器失效在 priority_queue 中表现得更隐蔽，因为它不暴露迭代器。调用方仍然可能持有 top() 返回的引用或从派生类、调试接口拿到底层容器引用。只要发生 push 或 pop，这些位置对象就应重新判断有效性；默认 vector 扩容会使所有旧位置失效，即使没有扩容，堆调整也会移动元素值。

24.4 make_heap、push_heap、pop_heap 与堆调整

heap 算法是理解 priority_queue 的源码入口。priority_queue 是封装后的接口，make_heap、push_heap、pop_heap 是直接操作随机访问区间的算法。C++ working draft 的 heap operations 条目把堆定义在随机访问范围上，并说明 push_heap 与 pop_heap 可以在对数时间内加入或移除根元素。

make_heap(first, last, comp) 把一个任意排列的区间重排成堆。它常用于从已有数据构造队列。对长度为 N 的区间，标准复杂度承诺是最多线性数量级的比较，具体上界是 3N 次比较。这使得“先收集一批元素再建堆”通常比逐个 push 更适合批量初始化。

push_heap(first, last, comp) 的前提是 [first, last - 1) 已经是堆，只有 last - 1 这个新位置尚未纳入堆。算法会把末尾元素沿父节点方向上浮，直到父节点不再排在它前面。它的比较次数是对数数量级，来源是新元素最多沿树高向上移动。

pop_heap(first, last, comp) 的前提是 [first, last) 是非空堆。算法会交换根位置和 last - 1，然后把 [first, last - 1) 修复成堆。调用后，原根元素位于末尾；调用方需要再执行容器层面的 pop_back() 才算真正删除元素。priority_queue::pop() 正是把这两个动作串起来。

下面的简化代码只展示上浮的核心路径。它属于教学用简化代码，用来说明 push_heap 为什么只需要沿父链移动。

template<class T, class Compare>
void teaching_sift_up(std::vector<T>& data, std::size_t child, Compare comp) {
    T value = std::move(data[child]);

    while (child > 0) {
        std::size_t parent = (child - 1) / 2;
        if (!comp(data[parent], value)) {
            break;
        }
        data[child] = std::move(data[parent]);
        child = parent;
    }

    data[child] = std::move(value);
}

在默认最大堆中，comp(data[parent], value) 等价于 data[parent] < value。条件成立时，新值优先级更高，父节点下移，新值继续向上。条件不成立时，父节点已经满足堆不变量，新值放在当前位置即可。

pop_heap 的下沉路径与上浮相反。根元素与末尾元素交换后，新的根可能低于某个孩子，于是算法把更适合做父节点的孩子上移，让根位置的候选值沿树向下移动。每一步只需要比较当前节点的两个孩子和候选值，所以成本同样受树高控制。

这些 heap 算法有两个常见误用边界。第一，push_heap 要求新元素已经位于末尾；只调用 push_heap 不会向容器追加元素。第二，pop_heap 不会缩短容器；它把原根移到末尾，删除动作由容器 pop_back 完成。调用方直接使用 heap 算法时，必须自己维护“容器大小变化”和“堆区间范围”这两个状态。

这也解释了 priority_queue 的价值。它把底层容器大小和 heap 区间边界绑定起来，调用者不需要每次手工写 data.push_back(x); std::push_heap(...) 或 std::pop_heap(...); data.pop_back()。封装减少了堆边界被调用方破坏的机会，同时也收窄了接口能力。

24.5 与 set 的区别和选型边界

priority_queue 和 set 都能让调用方接触某种“最值”，但它们的结构目标不同。priority_queue 用堆维护根元素，适合反复取当前最高优先级；set 用有序树维护全局有序关系，适合查找、遍历、删除指定元素和范围查询。

维度	priority_queue	set / multiset
底层模型	随机访问区间上的堆	节点式有序树的常见实现形状
主要目标	快速读取当前最高优先级	维护全局有序键空间
最值读取	top() 常数时间	begin() 或 rbegin() 常数时间
插入	push 对数时间，底层容器追加后堆调整	insert 对数时间，树路径插入与修复
删除当前最值	pop 对数时间	erase(begin()) 或 erase(prev(end())) 通常摊销常数到对数边界，取决于接口和实现
删除任意元素	无直接接口	可按迭代器或键删除
查找指定键	无直接接口	find、lower_bound、upper_bound
顺序遍历	无迭代器接口	支持有序遍历
同优先级稳定性	需要把 tie-breaker 编入元素	由键关系决定，multiset 允许等价元素
位置稳定性	默认 vector 调整会移动元素	节点式结构通常保持其他迭代器稳定

选型时先看操作集合。场景只需要“加入任务”和“取下一个任务”时，priority_queue 的接口更贴合目标，内存布局也更紧凑。场景需要取消指定任务、修改优先级、查询某个任务是否存在或按优先级遍历所有任务时，set、multiset 或“heap + 索引”的组合更合适。

任务调度示例中，如果任务入队后只会被执行，不需要取消，ReadyQueue 可以直接表达需求。如果任务可能被用户取消，单独的 priority_queue 会遇到定位问题：它找不到内部某个任务的位置。工程上常见的处理方式是维护任务 ID 到状态的哈希表，pop 时丢弃已取消任务；或者改用 set 保存可删除的有序任务节点。

优先级更新也是边界点。标准 priority_queue 没有 decrease-key 或 increase-key 接口。元素优先级改变后，原堆不变量可能失效；稳定做法是插入一个新版本，并在弹出时检查版本号，或者使用支持定位更新的堆结构。Dijkstra 最短路算法中常见的“重复入堆 + 弹出时跳过过期距离”就是这种 lazy deletion 思路。

set 的代价来自节点结构和指针跳转。它支持更丰富的有序操作，但每个元素通常需要单独节点、颜色或平衡信息以及左右父指针，缓存局部性通常弱于 vector 承载的堆。priority_queue 的代价来自接口收窄和任意位置操作缺席；它用更少的结构能力换取紧凑存储和简单最值路径。

因此可复用判断顺序是：先列出必须支持的操作，再判断是否需要任意元素定位和有序遍历；接着检查优先级是否会变化；最后比较元素数量、内存局部性、引用稳定性和取消策略。若操作集合集中在 push、top、pop，优先选择 priority_queue。若操作集合包含 find、erase(key)、lower_bound 或稳定节点引用，优先考虑 set / multiset 或复合结构。

24.6 工程使用场景

调度是 priority_queue 最直接的场景。任务系统、线程池、离散事件模拟和消息处理都可能持续产生候选任务，每次只取优先级最高的任务执行。这里的关键是维护当前堆顶正确，并让每次加入和弹出成本保持对数级；全量排序通常会制造额外成本。

延迟任务队列通常把时间戳作为优先级，并使用最小堆。堆顶是最早到期任务；如果堆顶还没到期，调度器可以等待对应时间差。如果需要取消任务，可以使用任务 ID 表记录状态，弹出堆顶时检查任务是否仍然有效。

struct TimerTask {
    long long due_time_ms;
    int id;
};

struct EarlierDueTime {
    bool operator()(const TimerTask& lhs, const TimerTask& rhs) const {
        return lhs.due_time_ms > rhs.due_time_ms;
    }
};

using TimerQueue = std::priority_queue<TimerTask, std::vector<TimerTask>, EarlierDueTime>;

这个比较器让 due_time_ms 更小的任务成为 top()。判断方法仍然相同：lhs.due_time_ms > rhs.due_time_ms 为 true 时，lhs 排在 rhs 前面，所以更晚到期的任务会输出得更晚，更早到期的任务会留在堆顶。

Top-K 是另一个典型场景。要在大量数据中保留最大的 K 个元素，可以维护一个大小最多为 K 的最小堆。堆顶是当前 K 个候选中最小的那个；新值大于堆顶时，弹出堆顶并插入新值。这样内存只与 K 成正比，每个有效替换成本是 O(log K)。

#include <functional>
#include <queue>
#include <vector>

std::vector<int> top_k_largest(const std::vector<int>& input, std::size_t k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;

    for (int value : input) {
        if (heap.size() < k) {
            heap.push(value);
        } else if (k != 0 && value > heap.top()) {
            heap.pop();
            heap.push(value);
        }
    }

    std::vector<int> result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    return result;
}

这段代码返回的 result 不保证降序或升序输出；它只保证元素集合来自最大的 K 个值。需要最终有序结果时，可以在收集后再排序，或者反向消费最小堆结果。这个边界来自 priority_queue 的接口语义：它保证每一步堆顶正确，不保证底层容器整体有序。

最短路算法也常用 priority_queue，尤其是 Dijkstra。标准 priority_queue 缺少 decrease-key，所以工程实现通常把新的更短距离再次压入队列，并在弹出时检查当前距离是否仍匹配记录表。这个策略增加了堆中的过期条目，但代码简单，且在很多稀疏图场景中表现稳定。

struct State {
    int distance;
    int vertex;
};

struct ShorterDistance {
    bool operator()(const State& lhs, const State& rhs) const {
        return lhs.distance > rhs.distance;
    }
};

using Frontier = std::priority_queue<State, std::vector<State>, ShorterDistance>;

当 Frontier 弹出一个状态时，算法应比较 state.distance 和当前记录的 dist[state.vertex]。若二者不同，这个状态已经过期，继续弹出下一个堆顶。这个 lazy deletion 判断弥补了标准 priority_queue 没有定位更新接口的边界。

工程上使用 priority_queue 时，按以下顺序检查即可：第一，确认需求是否只围绕当前最值推进；第二，确认比较器的方向和 tie-breaker；第三，确认元素优先级入队后是否会变化；第四，确认取消、查找、遍历是否需要额外索引；第五，确认底层容器的引用失效和元素移动成本是否可以接受。

最小自检任务

阅读下面代码，判断三次输出的任务名，并说明每次 push / pop 后队列内部需要维护什么不变量。

ReadyQueue ready;
ready.push(Task{3, 0, "tokenize"});
ready.push(Task{7, 1, "compile"});
ready.push(Task{7, 2, "link"});
ready.push(Task{5, 3, "package"});

std::cout << ready.top().name << '\n';
ready.pop();
std::cout << ready.top().name << '\n';
ready.pop();
std::cout << ready.top().name << '\n';

答案要点

输出顺序是 compile、link、package。TaskOrder 让 priority 更大的任务成为堆顶；compile 和 link 的优先级相同，sequence 更小的 compile 排在堆顶。第一次 pop 会把 compile 移到末尾并删除，然后修复剩余区间的堆不变量；第二次 top 读取新的根节点 link。第二次 pop 后，剩余任务中 package 的优先级高于 tokenize，所以第三次输出 package。

关键判断步骤是先解释 comp(lhs, rhs) 的含义，再把 top 理解为该弱序关系下排在最后的元素，最后按 push_heap 和 pop_heap 的状态路径追踪根节点变化。队列内部数组无需整体排序，只要每个父子关系满足 comp(parent, child) 为 false，top() 就能读取当前最高优先级元素。

本章知识点总结

• 适配器模型：std::priority_queue 用受限队列接口封装底层容器和 heap 算法。
• 堆不变量：随机访问区间成为堆时，每个父子关系都满足 comp(parent, child) 为 false。
• 默认方向：默认 std::less<T> 让弱序关系中排在最后的最大元素成为 top()。
• 最小堆写法：使用 std::greater<T> 或等价比较器可以让较小元素成为堆顶。
• 底层容器：底层容器需要随机访问迭代器，并提供 front()、push_back() 和 pop_back()。
• 比较器边界：比较器应表达严格弱序，并保持无副作用和稳定结果。
• push 路径：push 先追加元素，再通过 push_heap 让新元素沿父链上浮。
• pop 路径：pop 先通过 pop_heap 把原堆顶移到末尾，再用 pop_back 删除它。
• top 引用：top() 返回堆顶引用，后续 push 或 pop 后应重新获取位置。
• heap 算法：make_heap 服务批量建堆，push_heap 服务末尾新元素入堆，pop_heap 服务根元素移出堆区间。
• set 对比：priority_queue 适合最值推进，set / multiset 适合查找、删除指定元素和有序遍历。
• 更新策略：标准 priority_queue 缺少定位更新接口，优先级变化通常通过重新插入和过期检查处理。
• Top-K 场景：固定大小最小堆可以用 O(K) 空间维护数据流中的最大 K 个元素。
• 调度场景：任务调度和延迟队列适合用 priority_queue 表达“每次取下一个最高优先级元素”。