尧图网页设计 
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 Structurespb_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_queueT, Compare, Tag, Allocator由于类名与std::priority_queue重复使用时必须注明命名空间。官方文档的复杂度及常数测试可参考 GCC libstdc 的扩展文档页面pq_performance_tests。二、模板形参从元素类型到五种堆 Tag__gnu_pbds::priority_queue共四个模板形参形参含义T储存的元素类型Compare提供严格弱序的比较类型如std::lessT大根堆或std::greaterT小根堆Tag选择底层堆实现默认pairing_heap_tagAllocator空间配置器OI 中极少用到一般使用默认值其中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_queueint; // __gnu_pbds::priority_queueint, greaterint; // __gnu_pbds::priority_queueint, greaterint, pairing_heap_tag; __gnu_pbds::priority_queueint::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 决定了每个操作的时间复杂度pushpopmodifyeraseJoinpairing_heap_tag$O(1)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$$O(1)$binary_heap_tag最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$$\Theta(n)$$\Theta(n)$$\Theta(n)$binomial_heap_tag最坏 $\Theta(\log n)$均摊 $O(1)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$rc_binomial_heap_tag$O(1)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$thin_heap_tag$O(1)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(\log n)$均摊 $O(1)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$$\Theta(n)$这张表解释了各 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_queueint; 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_queueint::point_iterator。但不同 Tag 的底层实现不同迭代器的失效条件也不一样。根据__gnu_pbds库的设计失效保证分为由上至下派生的三个等级基本失效保证basic_invalidation_guarantee不修改容器时点类型迭代器point_iterator、指针和引用key/value保持有效。点失效保证point_invalidation_guarantee修改容器后点类型迭代器、指针和引用只要对应元素在容器中没被删除就保持有效。范围失效保证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_traitsT::invalidation_guarantee; cout abi::__cxa_demangle(typeid(gute).name(), 0, 0, 0) endl; } int main() { using pairing __gnu_pbds::priority_queueint, greaterint, pairing_heap_tag; using binary __gnu_pbds::priority_queueint, greaterint, binary_heap_tag; using binomial __gnu_pbds::priority_queueint, greaterint, binomial_heap_tag; using rc_binomial __gnu_pbds::priority_queueint, greaterint, rc_binomial_heap_tag; using thin __gnu_pbds::priority_queueint, greaterint, thin_heap_tag; print_invalidation_guaranteepairing(); print_invalidation_guaranteebinary(); print_invalidation_guaranteebinomial(); print_invalidation_guaranteerc_binomial(); print_invalidation_guaranteethin(); return 0; }从上述代码的输出可以得出结论除了binary_heap_tag为basic_invalidation_guarantee修改后迭代器会失效之外其余四种 Tag 均为point_invalidation_guarantee可以实现修改后点类型迭代器不失效的需求。这对算法竞赛有直接意义在 Dijkstra 等需要「保存每个点在堆中的位置、松弛后原地改键」的场景中应避免使用binary_heap_tag否则堆重排后保存的迭代器会指向失效位置产生难以排查的错误而默认的配对堆则能安全地支持这一套路。八、实战要点总结头文件与命名空间包含ext/pb_ds/priority_queue.hpp声明时写全__gnu_pbds::priority_queue...避免与std重名冲突。默认即最优竞赛中无特殊理由一律使用默认的pairing_heap_tag其余 Tag 常数或内存表现不佳容易 TLE / MLE。迭代器是灵魂push()保存返回值、modify(point_iterator, key)原地改键、erase(point_iterator)删除任意元素、join()实现 $O(1)$ 合并——这是std::priority_queue不具备的四大能力。失效保证要记牢binary_heap_tag修改后迭代器失效其余 Tag 满足point_invalidation_guarantee长生命周期迭代器场景务必避开二叉堆。配套阅读配对堆的数据结构原理与复杂度分析见 docs/ds/pairing-heap.mdpb_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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI 选手的 `__gnu_pbds::priority_queue` 实战指南：五种 Tag、迭代器失效保证与配对堆应用
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 Structurespb_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_queueT, Compare, Tag, Allocator由于类名与std::priority_queue重复使用时必须注明命名空间。官方文档的复杂度及常数测试可参考 GCC libstdc 的扩展文档页面pq_performance_tests。二、模板形参从元素类型到五种堆 Tag__gnu_pbds::priority_queue共四个模板形参形参含义T储存的元素类型Compare提供严格弱序的比较类型如std::lessT大根堆或std::greaterT小根堆Tag选择底层堆实现默认pairing_heap_tagAllocator空间配置器OI 中极少用到一般使用默认值其中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_queueint; // __gnu_pbds::priority_queueint, greaterint; // __gnu_pbds::priority_queueint, greaterint, pairing_heap_tag; __gnu_pbds::priority_queueint::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 决定了每个操作的时间复杂度pushpopmodifyeraseJoinpairing_heap_tag$O(1)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$$O(1)$binary_heap_tag最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$$\Theta(n)$$\Theta(n)$$\Theta(n)$binomial_heap_tag最坏 $\Theta(\log n)$均摊 $O(1)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$rc_binomial_heap_tag$O(1)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$thin_heap_tag$O(1)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$最坏 $\Theta(\log n)$均摊 $O(1)$最坏 $\Theta(n)$均摊 $\Theta(\log n)$$\Theta(n)$这张表解释了各 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_queueint; 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_queueint::point_iterator。但不同 Tag 的底层实现不同迭代器的失效条件也不一样。根据__gnu_pbds库的设计失效保证分为由上至下派生的三个等级基本失效保证basic_invalidation_guarantee不修改容器时点类型迭代器point_iterator、指针和引用key/value保持有效。点失效保证point_invalidation_guarantee修改容器后点类型迭代器、指针和引用只要对应元素在容器中没被删除就保持有效。范围失效保证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_traitsT::invalidation_guarantee; cout abi::__cxa_demangle(typeid(gute).name(), 0, 0, 0) endl; } int main() { using pairing __gnu_pbds::priority_queueint, greaterint, pairing_heap_tag; using binary __gnu_pbds::priority_queueint, greaterint, binary_heap_tag; using binomial __gnu_pbds::priority_queueint, greaterint, binomial_heap_tag; using rc_binomial __gnu_pbds::priority_queueint, greaterint, rc_binomial_heap_tag; using thin __gnu_pbds::priority_queueint, greaterint, thin_heap_tag; print_invalidation_guaranteepairing(); print_invalidation_guaranteebinary(); print_invalidation_guaranteebinomial(); print_invalidation_guaranteerc_binomial(); print_invalidation_guaranteethin(); return 0; }从上述代码的输出可以得出结论除了binary_heap_tag为basic_invalidation_guarantee修改后迭代器会失效之外其余四种 Tag 均为point_invalidation_guarantee可以实现修改后点类型迭代器不失效的需求。这对算法竞赛有直接意义在 Dijkstra 等需要「保存每个点在堆中的位置、松弛后原地改键」的场景中应避免使用binary_heap_tag否则堆重排后保存的迭代器会指向失效位置产生难以排查的错误而默认的配对堆则能安全地支持这一套路。八、实战要点总结头文件与命名空间包含ext/pb_ds/priority_queue.hpp声明时写全__gnu_pbds::priority_queue...避免与std重名冲突。默认即最优竞赛中无特殊理由一律使用默认的pairing_heap_tag其余 Tag 常数或内存表现不佳容易 TLE / MLE。迭代器是灵魂push()保存返回值、modify(point_iterator, key)原地改键、erase(point_iterator)删除任意元素、join()实现 $O(1)$ 合并——这是std::priority_queue不具备的四大能力。失效保证要记牢binary_heap_tag修改后迭代器失效其余 Tag 满足point_invalidation_guarantee长生命周期迭代器场景务必避开二叉堆。配套阅读配对堆的数据结构原理与复杂度分析见 docs/ds/pairing-heap.mdpb_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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考