pd_ds
需要
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace __gnu_cxx
__gnu_pbds::priority_queue
注意可能会与std::priority_queue冲突。
定义方法:__gnu_pbds ::priority_queue<T, Compare, Tag, Allocator>
-
T:类型名
-
Compare:严格弱化的比较类型
-
Tag:
__gnu_pbds提供的五种堆，默认为pairing_heap_tag-
pairing_heap_tag:配对堆(配对堆是一个支持插入，查询/删除最小值，合并，修改元素等操作的数据结构，是一种可并堆。有速度快和结构简单的优势，但由于其为基于势能分析的均摊复杂度，无法可持久化)。在实际测试中表现最好。 -
binary_heap_tag:二叉堆，表现并不是如官方文档说的那么好。 -
binomial_heap_tag:二项堆(二项堆（binomial heap）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（mergeable heap）抽象数据类型的一种。)，合并操作时表现优于二叉堆，取堆顶元素的复杂度比二叉堆高。 -
rc_binomial_heap_tag:冗余计数二项堆，表现貌似比二项堆好点。 -
thin_heap_tag:除了合并是\(O(n)\)的，其它和斐波那契堆一样。综合来看，Tag中默认的
pairing_heap_tag综合表现最好，竞赛中常用的也是这个。
-
-
Allocator:空间配置器，不造是啥，反正在竞赛中基本不会设计，想了解的大佬建议百度
成员函数:
- push():向堆中压入一个元素并返回改元素位置的迭代器
- pop():弹出堆顶
- top():返回堆顶元素
- size():返回元素个数
- empty():返回是否为空
- modify(iterator ,key)将迭代器位置的
key变为传入的key，并排序 - erase(iterator):删除迭代器处的键值
- join(__gnu_pbds::priority_queue &other):将
other合并到*this中并将other清空