std :: priority_queue

#include <queue> // std :: priority_queue// using namespace std; 推荐根据不同的使用分别using,而不是直接using std; 为了方便区别与pb_ds,// 本文里的所有优先队列都会加上命名空间std :: priority_queue<T, Container, Compare>/* * T : 储存的元素类型 * Container : 储存的容器类型,且要求满足顺序容器的要求、随机访问迭代器的要求、拥有 * front()/push_back()/pop_back()三个函数,标准容器中 std :: vector / std :: deque满足这些要求 * Compare : 提供严格的弱序比较类型 * priority_queue是按照元素优先级大的在堆顶,根据operator < 的定义,默认是大根队,我们可以利用 * greater<T>(若支持),或者自定义类的小于号重载实现排序,注意 : 只支持小于号重载而不支持其他比较符号的重 * 载 */// 构造方式 :std :: priority_queue<int>;std :: priority_queue<int, vector<int>> // C++11前,vector<int>" ">双引号位置必须要有空格std :: priority_queue<int, deque<int>, greater<int>> //注意 :不可跳过容器参数而直接传入比较类
成员函数 :
  1. top(): 访问栈顶元素 常数复杂度
  2. empty(): 检查底层的容器是否为空 常数复杂度
  3. size(): 返回底层容器的元素数量 常数复杂度
  4. push(): 插入元素,并对底层容器排序 最坏$\Theta(n)$ 均摊$\Theta(\log(n))$
  5. pop(): 删除第一个元素 最坏$\Theta(\log(n))$

由于std :: priority_queue原生不支持modify() /join()/erase()故不做讲解。

__gnu_pbds :: priority_queue

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

#include <ext/pb_ds/priority_queue.hpp>using namespace __gnu_pbds;__gnu_pbds :: priority_queue<T, Compare, Tag, Allocator> // 由于OI中很少出现空间配置器,故这里不做讲解(其实是我也不知道是啥,逃/* * T : 储存的元素类型 * Compare : 提供严格的弱序比较类型 * Tag : 是__gnu_pbds提供的不同的五种堆,Tag参数默认是 pairing_heap_tag * 五种分别是 : * pairing_heap_tag -> 配对堆 // 官方文档认为在非原生元素(如自定义结构体/ std :: string / pair)中 * pairing heap表现的最好 * binary_heap_tag -> 二叉堆 // 官方文档认为在原生元素中 二叉堆表现最好,不过我测试的表现并没有那么好 * binomial_heap_tag -> 二项堆 // 二项堆在合并操作的表现要优于配对堆* 但是其取堆顶元素的 * rc_binomial_heap_tag -> 冗余计数二项堆 * thin_heap_tag -> 除了合并的复杂度都和Fibonacci堆一样的一个tag * 由于本篇文章只是提供给学习算法竞赛的同学们,故对于后四个tag只会简单的介绍复杂度,第一个会介绍成员函数和 * 使用方法,经作者本机 Core i5@3.1 GHz On macOS 测试堆的基础操作/结合GNU官方的复杂度测试/Dijkstra * 测试,都表明至少对于OIer来讲,除了配对堆的其他4个tag都是鸡肋,不是没什么用就是常数大到不如std的*且有可 * 能造成MLE * priority_queue,故这里只推荐用默认的pairing_heap。 * 同样,配对堆也优于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> // 迭代器 :迭代器是一个内存地址,在modify和push的时候都会返回一个迭代器,下文会详细的讲使用方法 __gnu_pbds :: priority_queue<int> :: point_iterator id; id = q.push(1);

复杂度如下表 :

pushpopmodifyeraseJoin
Pairing_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)$ 0均摊$\Theta(\log(n))$$\Theta(n)$
成员函数:(std::priority_queue出现过的不再解释)
  1. modify(point_iterator, const key) : 把迭代器位置的key修改为传入的key,并对底层储存结构进行排序
  2. erase(point_iterator) : 把迭代器位置的键值从堆中擦除
  3. join(__gnu_pbds :: priority_queue &other):把other合并到*this并把other清空。
pb_ds的堆甚至可以和手写的速度相媲美,如果有卡常需要或者配对堆需要可以方便的使用。
作者用配对堆优化的Dijkstra在BZOJ的3040跑到了Rank5(偷偷怀疑Rank1特判数据哦)