今年暑假外校集训的时候一道题标算是最短路扩展，然而std用的是pbds，于是就产生了研究的兴趣。结果那个标程我现在死都找不到了233
定义：
在知乎上看到有oier去年向CCF发了邮件，得到的回复是pbds库可以用，但是不能写这句话：
using namespace __gnu_pbds;
存图为证。
--------------------------------------------------------------------------原答案分割线--------------------------------------------------------------------------------------------------------------------------------------
pbds是一个封装了众多高效又实用（相对于STL）的数据结构的库，包括堆，平衡树，哈希表等。然而目前仍然不清楚NOIP中能否使用。在CCF2011年发布的关于NOI系列赛编程语言使用限制的规定中明确规定C/C++程序禁止使用内嵌汇编和以下划线开头的库函数或宏（自己定义的除外），然而在WC2015营员交流中一位同学却说pbds在NOI系列赛事中可以使用，这就造成了现在的这种尴尬境地。
由于本人实在蒟蒻，加上pbds的平衡树在维护有序序列时对存在重复元素的情况维护难度较大，且该问题用STL中的vector就可以妥善解决，（之前自己智障），在此只介绍pbds中堆的用法。
用法：
由于bits/stdc++.h不覆盖pbds，使用时需加上#include<ext/pb_ds/priority_queue.hpp>和using namespace __gnu_pbds;（gnu前两条下划线）。（命名空间不能使用）
注意：pbds的堆在定义时不需要vector<int>。
定义一个int类型的小根堆：__gnu_pbds::priority_queue<int,greater<int>,TAG>pq;
TAG指明了所用堆的类型，共有以下几种：
pairing_heap_tag：配对堆
thin_heap_tag：斐波那契堆
binomial_heap_tag：二项堆
binary_heap_tag：二叉堆
如果是大根堆的话只需要去掉greater<int>即可，也可以定义结构体类型或者其他类型，只要重载了<运算符就可以使用。
这些堆普遍支持push,pop,top和join操作。最后一个操作是将两个堆合并，使用方法：a.join(b);//将堆b合并至堆a中
配对堆和斐波那契堆的理论复杂度均十分优异，push,top,join都能做到均摊O(1),pop能做到O(logn)。
二项堆的各种操作复杂度都是O(logn)。二叉堆的复杂度不知，但实际运行速度极慢，反而不如std和手写堆，不知是何原因，不建议使用。
拿一道最短路例题来测试一下各种堆的速度吧：
例题：
Luogu P3371 【模板】单源最短路径 题目链接
题意：给定一张n个点，m条边的有向图和起点s，要求输出s到每个点的最短距离，若不可达输出2147483647。
数据范围：n<=10000,m<=500000。
题解：SPFA或dijkstra堆优化。
配对堆：756ms
斐波那契堆：664ms
二项堆：812ms
二叉堆：1516ms+3TLE
TAG留空（我也不知道这是什么骚操作）：586ms
基本符合理论复杂度。在平时或者考场上时建议使用配对堆或斐波那契堆或者直接留空。