前言
之前我一直都这么以为：$Fibonacci$堆虽然快，但是代码复杂度反人类；二项堆打起来麻烦的死，而且又难理解又难调；综合起来还是左偏树最好！！！
直到我知道了配对堆这个东西。。。。。。
我$HolseLee$就是省选爆零，暴力分都拿不到，也绝不会学左偏树以外的可并堆！呵呵，配对堆真快，爆了左偏树几条街呢。
配对堆
以下部分内容及图片引用自：
https://www.cnblogs.com/Paul-Guderian/p/7664366.html
定义
配对堆（$Pairing Heap$）也是属于可并堆的一种，是一棵多叉树。也可以说它是$Fibonacci$堆的简化版本，和$Fibonacci$堆一样，其操作复杂度及其优秀，而且代码复杂度又非常低，与左偏树基本一致，是$OI$比赛的好选择。
基本操作
合并（$merge$）：$O(1)$
插入新节点（$push$）：$O(1)$
修改值（$change$）：$O(1)/O(log n)$
取出堆顶元素（$top$）：$O(1)$
删除堆顶元素（$pop$）：$O(log n)$
合并
可并堆最重要的操作，直接比较两个需要合并的堆的堆顶然后按照大小关系连边就行了。复杂度低到惊人的$O(1)$；
插入新节点
可以把新节点看作一个只有一个元素的堆，再与当前堆合并就行了。
取出堆顶元素
直接返回堆顶值即可。
修改值
如何修改一个点的值呢？首先将这个点与父节点之间的连边断开，即令$fa[u]=0$，（如果用邻接链表存边不方便断边就可以不断，因为除了连边以外，判断父子关系还需要子节点的$fa[]$指向父节点，因此不断边实际上也不会有问题）然后修改值即可。
断掉与父亲的连边后,相当于形成两个堆,接下来进行一次$merge$操作就好了。可以发现这个操作的时间复杂度是$O(1)$，但有资料认为这个操作可能会破坏配对堆应有的结构(这"应有"的结构在下文会体现出来,它是$pop$操作复杂度是$O(log n)$而不是$O(n)$的重要保证),结构改变后就会影响$pop$的复杂度,使其向$O(n)$退化,因此计算后认定其实修改操作从时间复杂度贡献分析来看,可能是$O(log n)$而不是$O(1)$。
不过反正这个操作比较少用就是了。
删除堆顶元素
可以发现，以上的操作基本上就像蛇皮怪一样的瞎$merge$连个边就了事了，所以复杂度就全部承受在这个操作上了（爱谴责人士表示强烈$pop$）。
现在需要删除根节点，如果直接把根节点删掉然后把它的子节点一个个连起来的话，可能会使新的根节点有多个子节点然后影响后面的复杂度，使得后面$pop$操作复杂度退化成$O(n)$。较优秀的方法应该是将子节点两两$merge$，直到全部合并在一起为止。这样可以保证后面的复杂度不会退化。
模板代码
照着网上的大佬自己瞎几把打了一份，打的不好看将就着看吧。
Code：
//It is made by HosleLee on 25th Oct 2018 //Pairing_Heap #include<bits/stdc++.h> using namespace std; const int N=1e5+7; int n,m,val[N],head[N],cnte,fa[N]; struct Edge { int to,nxt; }e[N<<1]; queue<int>q; inline int read() { char ch=getchar(); int x=0; bool flag=false; while( ch<'0' || ch>'9' ) { if( ch=='-' ) flag=true; ch=getchar(); } while( ch>='0' && ch<='9' ) { x=x*10+ch-'0'; ch=getchar(); } return flag ? -x : x; } inline int find(int x) { if( fa[x]==-1 ) return 0; while( fa[x]!=x ) x=fa[x]; return x; } inline void add(int x,int y) { e[++cnte].to=y, e[cnte].nxt=head[x]; head[x]=cnte; fa[y]=x; } inline int neo(int x,int i) { val[i]=x; return i; } inline int merge(int x,int y) { if( !x || !y ) return x+y; if( val[x]<val[y] || (val[x]==val[y] && x<y ) ) return add(x,y),x; return add(y,x),y; } inline void pop(int rt) { int x,y; for(int i=head[rt]; i; i=e[i].nxt) if( fa[y=e[i].to]==rt ) q.push(y), fa[y]=y; fa[rt]=-1; while( q.size()>1 ) { x=q.front(), q.pop(); y=q.front(), q.pop(); q.push(merge(x,y)); } if( !q.empty() ) q.pop(); } inline void top(int x) { if( !x ) { printf("-1 "); return; } printf("%d ",val[x]); pop(x); } int main() { n=read(); m=read(); for(int i=1; i<=n; ++i) fa[i]=neo(read(),i); int opt; for(int i=1; i<=m; ++i) { opt=read(); if( opt==1 ) merge(find(read()),find(read())); else top(find(read())); } return 0; }
总结
学完配对堆以后，我突然发现好像左偏树除了可持久化以外貌似一无是处了（复杂度完全被吊打233333）？？？？？？
当然不是，因为左偏树结构非常稳定，方便套用其他不常用的一些操作，所以根据情况选择算法就行了，各种算法都各有各的优劣。（顺便推荐一波我的另一篇左偏树的博客23333）
最后附上一张各种堆比较的表格：
