STL: Priority_queue – [讲解/原创]

std :: priority_queue

#include  // std :: priority_queue
// using namespace std; 推荐根据不同的使用分别using,而不是直接using std; 为了方便区别与pb_ds,
// 本文里的所有优先队列都会加上命名空间
std :: priority_queue
/*
 * T : 储存的元素类型
 * Container : 储存的容器类型,且要求满足顺序容器的要求、随机访问迭代器的要求、拥有
 * front()/push_back()/pop_back()三个函数,标准容器中 std :: vector / std :: deque满足这些要求
 * Compare : 提供严格的弱序比较类型
 * priority_queue是按照元素优先级大的在堆顶,根据operator < 的定义,默认是大根队,我们可以利用
 * greater(若支持),或者自定义类的小于号重载实现排序,注意 : 只支持小于号重载而不支持其他比较符号的重
 *  载
 */
// 构造方式 :
std :: priority_queue;
std :: priority_queue> // C++11前,vector" ">双引号位置必须要有空格
std :: priority_queue, greater> //注意 :不可跳过容器参数而直接传入比较类
成员函数 :
  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 
using namespace __gnu_pbds;
__gnu_pbds :: priority_queue // 由于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
 __gnu_pbds :: priority_queue>
 __gnu_pbds :: priority_queue, pairing_heap_tag>
 // 迭代器 :迭代器是一个内存地址,在modify和push的时候都会返回一个迭代器,下文会详细的讲使用方法
 __gnu_pbds :: priority_queue :: point_iterator id;
 id = q.push(1);

复杂度如下表 :

push pop modify erase Join
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特判数据哦)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注