__gnu_pbds :: priority_queue

附:官方文档地址——复杂度及常数测试

模板形参

  • T: 储存的元素类型
  • Compare: 提供严格的弱序比较类型
  • Tag: 是 __gnu_pbds 提供的不同的五种堆,Tag 参数默认是 pairing_heap_tag 五种分别是:
    • pairing_heap_tag:配对堆 官方文档认为在非原生元素(如自定义结构体/std :: string/pair) 中,配对堆表现最好
    • binary_heap_tag:二叉堆 官方文档认为在原生元素中二叉堆表现最好,不过我测试的表现并没有那么好
    • binomial_heap_tag:二项堆 二项堆在合并操作的表现要优于二叉堆,但是其取堆顶元素操作的复杂度比二叉堆高
    • rc_binomial_heap_tag:冗余计数二项堆
    • thin_heap_tag:除了合并的复杂度都和 Fibonacci 堆一样的一个 tag
  • Allocator:空间配置器,由于 OI 中很少出现,故这里不做讲解

由于本篇文章只是提供给学习算法竞赛的同学们,故对于后四个 tag 只会简单的介绍复杂度,第一个会介绍成员函数和使用方法。

经作者本机 Core i5 @3.1 GHz On macOS 测试堆的基础操作,结合 GNU 官方的复杂度测试,Dijkstra 测试,都表明: 至少对于 OIer 来讲,除了配对堆的其他四个 tag 都是鸡肋,要么没用,要么常数大到不如 std 的,且有可能造成 MLE,故这里只推荐用默认的配对堆。同样,配对堆也优于 algorithm 库中的 make_heap()

构造方式

要注明命名空间因为和 std 的类名称重复。

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

成员函数

  • push(): 向堆中压入一个元素,返回该元素位置的迭代器。
  • pop(): 将堆顶元素弹出。
  • top(): 返回堆顶元素。
  • size() 返回元素个数。
  • empty() 返回是否非空。
  • modify(point_iterator, const key): 把迭代器位置的 key 修改为传入的 key,并对底层储存结构进行排序。
  • erase(point_iterator): 把迭代器位置的键值从堆中擦除。
  • join(__gnu_pbds :: priority_queue &other): 把 other 合并到 *this 并把 other 清空。

使用的 tag 决定了每个操作的时间复杂度:

pushpopmodifyeraseJoin
pairing_heap_tag最坏 均摊 最坏 均摊 最坏 均摊
binary_heap_tag最坏 均摊 最坏 均摊
binomial_heap_tag最坏 均摊
rc_binomial_heap_tag
thin_heap_tag最坏 均摊 最坏 均摊 最坏 0 均摊

示例

__gnu_pbds 迭代器的失效保证(invalidation_guarantee)

在上述示例以及一些实践中(如使用本章的 pb-ds 堆来编写单源最短路等算法),常常需要保存并使用堆的迭代器(如 __gnu_pbds::priority_queue<int>::point_iterator 等)。

可是例如对于 __gnu_pbds::priority_queue 中不同的 Tag 参数,其底层实现并不相同,迭代器的失效条件也不一样,根据__gnu_pbds 库的设计,以下三种由上至下派生的情况:

  1. 基本失效保证(basic_invalidation_guarantee):即不修改容器时,点类型迭代器(point_iterator)、指针和引用(key/value)保持 有效。

  2. 点失效保证(point_invalidation_guarantee):即 修改 容器后,点类型迭代器(point_iterator)、指针和引用(key/value)只要对应在容器中没被删除 保持 有效。

  3. 范围失效保证(range_invalidation_guarantee):即 修改 容器后,除(2)的特性以外,任何范围类型的迭代器(包括 begin()end() 的返回值)是正确的,具有范围失效保证的 Tag 有 rb_tree_tag 和 适用于 __gnu_pbds::tree 的 splay_tree_tag(),以及 适用于 __gnu_pbds::trie 的 pat_trie_tag。

从运行下述代码中看出,除了 binary_heap_tagbasic_invalidation_guarantee 在修改后迭代器会失效,其余的均为 point_invalidation_guarantee 可以实现修改后点类型迭代器 (point_iterator) 不失效的需求。

贡献者:@Stanley@Dejia@忘怀@Ir1dXD@CoderOJ@mgt@H-J-Granger@Xeonacid

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组