堆
__gnu_pbds :: priority_queue
1 2 3 |
|
模板形参
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
的类名称重复。
1 2 3 4 5 |
|
成员函数
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 决定了每个操作的时间复杂度:
push | pop | modify | erase | Join | |
---|---|---|---|---|---|
pairing_heap_tag |
最坏 |
最坏 |
最坏 |
||
binary_heap_tag |
最坏 |
最坏 |
|||
binomial_heap_tag |
最坏 |
||||
rc_binomial_heap_tag |
|||||
thin_heap_tag |
最坏 |
最坏 |
最坏 |
示例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
__gnu_pbds 迭代器的失效保证(invalidation_guarantee)
在上述示例以及一些实践中(如使用本章的 pb-ds 堆来编写单源最短路等算法),常常需要保存并使用堆的迭代器(如 __gnu_pbds::priority_queue<int>::point_iterator
等)。
可是例如对于 __gnu_pbds::priority_queue
中不同的 Tag 参数,其底层实现并不相同,迭代器的失效条件也不一样,根据__gnu_pbds 库的设计,以下三种由上至下派生的情况:
-
基本失效保证(basic_invalidation_guarantee):即不修改容器时,点类型迭代器(point_iterator)、指针和引用(key/value)保持 有效。
-
点失效保证(point_invalidation_guarantee):即 修改 容器后,点类型迭代器(point_iterator)、指针和引用(key/value)只要对应在容器中没被删除 保持 有效。
-
范围失效保证(range_invalidation_guarantee):即 修改 容器后,除(2)的特性以外,任何范围类型的迭代器(包括
begin()
和end()
的返回值)是正确的,具有范围失效保证的 Tag 有rb_tree_tag
和 适用于__gnu_pbds::tree
的splay_tree_tag
,以及 适用于__gnu_pbds::trie
的pat_trie_tag
。
从运行下述代码中看出,除了 binary_heap_tag
为 basic_invalidation_guarantee
在修改后迭代器会失效,其余的均为 point_invalidation_guarantee
可以实现修改后点类型迭代器 (point_iterator) 不失效的需求。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
本页面最近更新:2023/9/1 16:49:46,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:GoodCoder666, Ir1d, opsiff, ouuan, Xeonacid, abc1763613206, Chrogeek, CoderOJ, countercurrent-time, Early0v0, Enter-tainer, H-J-Granger, i-Yirannn, ksyx, NachtgeistW, Planet6174, SukkaW, Tiphereth-A, WAAutoMaton
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用