企业官网建设流程全解析

OI 选手的__gnu_pbds::priority_queue实战指南：五种 Tag、迭代器失效保证与配对堆应用

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

__gnu_pbds::priority_queue是 GNU libstdc++ 的 Policy-Based Data Structures（pb_ds）库提供的优先队列实现，相比std::priority_queue，它多出了modify（改键）、erase（删任意元素）、join（可并堆合并）等关键能力，是 OI / ICPC 竞赛中实现可修改堆、可并堆、Dijkstra 堆优化等算法的利器。本文以 docs/lang/pb-ds/pq.md 为主体，系统讲解其模板形参、五种堆 Tag 的选择、成员函数与复杂度、完整可运行示例，并结合 配对堆原理 与 pb_ds 库总览 深入解析底层实现与迭代器失效保证，帮助读者理解「为什么竞赛中推荐默认使用配对堆」。

一、pb_ds 库与__gnu_pbds::priority_queue的定位

pb_ds 库全称Policy-Based Data Structures，封装了哈希表、平衡二叉树、字典树（Trie）、堆（优先队列）等数据结构。与vector、set、map一样，其组件符合 STL 接口规范，部分组件（如优先队列）包含 STL 内对应组件的所有功能，但功能更多——例如可以increase_key/decrease_key（改键）、删除单个元素，这正是 std 优先队列做不到的。相关背景参见 docs/lang/pb-ds/index.md。

使用它需要注意两点前提：

• 编译器依赖：pb_ds 只在以 libstdc++ 为标准库的编译器（GCC/g++）下可用，MSVC 等其他标准库环境下无法编译。
• 竞赛合规性：pb_ds 的主要内容位于以下划线开头的__gnu_pbds命名空间中。2021 年 9 月 1 日《关于 NOI 系列活动中编程语言使用限制的补充说明》允许使用以下划线开头的库函数或宏（明确禁止操作的除外），此后在 NOI 系列活动中使用 pb_ds 库有了文件层面的依据。

__gnu_pbds::priority_queue的声明如下：

#include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; __gnu_pbds::priority_queue<T, Compare, Tag, Allocator>

由于类名与std::priority_queue重复，使用时必须注明命名空间。官方文档的复杂度及常数测试可参考 GCC libstdc++ 的扩展文档页面（pq_performance_tests）。

二、模板形参：从元素类型到五种堆 Tag

__gnu_pbds::priority_queue共四个模板形参：

其中Tag决定底层数据结构，__gnu_pbds共提供五种：

• pairing_heap_tag（配对堆，默认）：官方文档认为在非原生元素（如自定义结构体、std::string、std::pair）中，配对堆表现最好。
• binary_heap_tag（二叉堆）：官方文档认为在原生元素中二叉堆表现最好（但本仓库文档作者实测表现并不理想）。
• binomial_heap_tag（二项堆）：合并操作优于二叉堆，但取堆顶元素（top）的复杂度比二叉堆更高。
• rc_binomial_heap_tag（冗余计数二项堆）：二项堆的一种变体，优化了插入的均摊复杂度。
• thin_heap_tag（瘦堆）：除合并外，各项复杂度与 Fibonacci 堆一致。

从底层实现看，配对堆是一棵满足堆性质的带权多叉树（每个节点权值不大于其所有儿子），通常用「儿子 - 兄弟表示法」储存，节点仅维护第一个儿子的指针与右兄弟指针，不维护任何额外的树大小、深度、排名等信息；而二叉堆依赖严格的完全二叉树结构保证复杂度，二项堆/冗余计数二项堆则需要维护额外的树结构，Fibonacci 堆式结构更是因为维护大量额外信息导致常数较大。这也是配对堆在竞赛实践中效率出色的结构原因，具体推导可阅读 docs/ds/pairing-heap.md。

三、如何选择 Tag：为什么竞赛只推荐默认配对堆

本文面向算法竞赛（OI）读者，对后四个 Tag 只作复杂度层面的简单介绍，而第一个（配对堆）则详细介绍成员函数与使用方法。理由是，结合作者在 Core i5 @3.1 GHz macOS 上的本机基准测试、GNU 官方复杂度测试以及 Dijkstra 测试，结论一致：对于 OIer 而言，除配对堆外的其他四个 Tag 都是「鸡肋」——要么用处不大，要么常数大到不如std的对应实现，甚至可能造成 MLE（内存超限）。因此本文只推荐使用默认的pairing_heap_tag；同时配对堆的常数表现也优于<algorithm>库中的make_heap()。

四、构造方式与迭代器

构造时需注明命名空间，避免与std::priority_queue重名冲突：

// __gnu_pbds::priority_queue<int>; // __gnu_pbds::priority_queue<int, greater<int>>; // __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag>; __gnu_pbds::priority_queue<int>::point_iterator id; // 点类型迭代器 // 在 modify 和 push 的时候都会返回一个 point_iterator，下文会详细的讲使用方法 id = q.push(1);

这里的关键概念是point_iterator（点类型迭代器）：push()会返回新元素位置的迭代器，modify()也接受迭代器作为参数。正是这个迭代器机制，让__gnu_pbds::priority_queue能够实现 std 优先队列无法做到的「修改堆内任意元素」与「删除堆内任意元素」。

五、成员函数全解

• push()：向堆中压入一个元素，返回该元素位置的迭代器。
• pop()：将堆顶元素弹出。
• top()：返回堆顶元素。
• size()：返回元素个数。
• empty()：返回是否为空。
• modify(point_iterator, const key)：把迭代器位置的key修改为传入的key，并自动对底层储存结构进行重新排序（即支持increase_key/decrease_key类操作）。
• erase(point_iterator)：把迭代器位置的键值从堆中擦除。
• join(__gnu_pbds::priority_queue &other)：把other合并到*this，合并后other被清空——这是「可并堆」的核心操作。

五种 Tag 的操作复杂度对照表

使用的 Tag 决定了每个操作的时间复杂度：

这张表解释了各 Tag 的适用场景与短板：配对堆以 $O(1)$ 的push与Join、均摊 $\Theta(\log n)$ 的pop/modify/erase取得全面平衡；二项堆与冗余计数二项堆的Join是 $\Theta(\log n)$ 而非 $O(1)$；瘦堆的modify均摊可达 $O(1)$ 但Join高达 $\Theta(n)$。另外需注意，配对堆基于势能分析的均摊复杂度决定了其无法可持久化，这一点与 docs/ds/pairing-heap.md 中对配对堆的定义描述一致。

六、完整示例：从 push 到 join 的全流程

以下完整示例演示了push/pop/top/modify/erase/join的全部用法（以面向 OIer 的常用堆pairing_heap_tag为范例，并定义宏以便阅读）：

#include <algorithm> #include <cstdio> #include <ext/pb_ds/priority_queue.hpp> #include <iostream> using namespace __gnu_pbds; // 由于面向OIer, 本文以常用堆 : pairing_heap_tag作为范例 // 为了更好的阅读体验，定义宏如下 ： using pair_heap = __gnu_pbds::priority_queue<int>; pair_heap q1; // 大根堆, 配对堆 pair_heap q2; pair_heap::point_iterator id; // 一个迭代器 int main() { id = q1.push(1); // 堆中元素 ： [1]; for (int i = 2; i <= 5; i++) q1.push(i); // 堆中元素 : [1, 2, 3, 4, 5]; std::cout << q1.top() << std::endl; // 输出结果 : 5; q1.pop(); // 堆中元素 : [1, 2, 3, 4]; id = q1.push(10); // 堆中元素 : [1, 2, 3, 4, 10]; q1.modify(id, 1); // 堆中元素 : [1, 1, 2, 3, 4]; std::cout << q1.top() << std::endl; // 输出结果 : 4; q1.pop(); // 堆中元素 : [1, 1, 2, 3]; id = q1.push(7); // 堆中元素 : [1, 1, 2, 3, 7]; q1.erase(id); // 堆中元素 : [1, 1, 2, 3]; q2.push(1), q2.push(3), q2.push(5); // q1中元素 : [1, 1, 2, 3], q2中元素 : [1, 3, 5]; q2.join(q1); // q1中无元素，q2中元素 ：[1, 1, 1, 2, 3, 3, 5]; }

注意观察modify的妙用：q1.modify(id, 1)把id指向的键值 10 原地改为 1，堆自动重新排序，且之后q1.top()正确返回 4——这正是 Dijkstra 堆优化中「松弛后更新堆内点距离」所必需的能力。

七、迭代器失效保证（invalidation_guarantee）

在示例以及实践（例如使用 pb_ds 堆编写单源最短路等算法）中，常常需要保存并使用堆的迭代器（如__gnu_pbds::priority_queue<int>::point_iterator）。但不同 Tag 的底层实现不同，迭代器的失效条件也不一样。根据__gnu_pbds库的设计，失效保证分为由上至下派生的三个等级：

1. 基本失效保证（basic_invalidation_guarantee）：不修改容器时，点类型迭代器（point_iterator）、指针和引用（key/value）保持有效。
2. 点失效保证（point_invalidation_guarantee）：修改容器后，点类型迭代器、指针和引用只要对应元素在容器中没被删除，就保持有效。
3. 范围失效保证（range_invalidation_guarantee）：修改容器后，除第 2 条特性外，任何范围类型迭代器（包括begin()和end()的返回值）仍然正确。具有范围失效保证的 Tag 有rb_tree_tag、适用于__gnu_pbds::tree的splay_tree_tag，以及适用于__gnu_pbds::trie的pat_trie_tag（注意这三者属于树形结构，不在堆的范畴内，堆相关的可参考 docs/lang/pb-ds/tree.md 了解tree的 Tag 体系）。

运行下面的程序即可在编译期打印每种 Tag 的失效保证类型：

#include <iostream> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; #include <cxxabi.h> template <typename T> void print_invalidation_guarantee() { using gute = __gnu_pbds::container_traits<T>::invalidation_guarantee; cout << abi::__cxa_demangle(typeid(gute).name(), 0, 0, 0) << endl; } int main() { using pairing = __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag>; using binary = __gnu_pbds::priority_queue<int, greater<int>, binary_heap_tag>; using binomial = __gnu_pbds::priority_queue<int, greater<int>, binomial_heap_tag>; using rc_binomial = __gnu_pbds::priority_queue<int, greater<int>, rc_binomial_heap_tag>; using thin = __gnu_pbds::priority_queue<int, greater<int>, thin_heap_tag>; print_invalidation_guarantee<pairing>(); print_invalidation_guarantee<binary>(); print_invalidation_guarantee<binomial>(); print_invalidation_guarantee<rc_binomial>(); print_invalidation_guarantee<thin>(); return 0; }

从上述代码的输出可以得出结论：除了binary_heap_tag为basic_invalidation_guarantee（修改后迭代器会失效）之外，其余四种 Tag 均为point_invalidation_guarantee，可以实现修改后点类型迭代器不失效的需求。这对算法竞赛有直接意义：在 Dijkstra 等需要「保存每个点在堆中的位置、松弛后原地改键」的场景中，应避免使用binary_heap_tag，否则堆重排后保存的迭代器会指向失效位置，产生难以排查的错误；而默认的配对堆则能安全地支持这一套路。

八、实战要点总结

1. 头文件与命名空间：包含<ext/pb_ds/priority_queue.hpp>，声明时写全__gnu_pbds::priority_queue<...>，避免与std重名冲突。
2. 默认即最优：竞赛中无特殊理由一律使用默认的pairing_heap_tag，其余 Tag 常数或内存表现不佳，容易 TLE / MLE。
3. 迭代器是灵魂：push()保存返回值、modify(point_iterator, key)原地改键、erase(point_iterator)删除任意元素、join()实现 $O(1)$ 合并——这是std::priority_queue不具备的四大能力。
4. 失效保证要记牢：binary_heap_tag修改后迭代器失效，其余 Tag 满足point_invalidation_guarantee；长生命周期迭代器场景务必避开二叉堆。
5. 配套阅读：配对堆的数据结构原理与复杂度分析见 docs/ds/pairing-heap.md；pb_ds 库整体介绍（含 NOI 合规性说明）见 docs/lang/pb-ds/index.md；同库的__gnu_pbds::tree（含order_of_key、find_by_order等）见 docs/lang/pb-ds/tree.md。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki