前言可合并的堆包括二叉堆、二元堆、配对堆和斐波那契堆。 光是合并二叉堆也有大脑启发式合并、左倾树、斜堆等方法。
这里主要是关于两股山，关于其他优秀的并列山，请看DSCN优秀的博客吧。
每次使用启发式合并优先队列，逐个取出小堆的点合并成大堆时，复杂度将o(O(log2n ) o ) log^2n ) o ) log2n )平均除法。
优点：思路简单清晰，非常容易实现。
坏处：主要是太晚了。 其次，只允许普通的合并和跳出，其他奇怪的操作可能会破坏均摊的复杂性。
代码很简单，不会出水。
左倾树是最标准的常用做法，复杂度非常好。
为普通二叉山(不平衡)的每个节点定义“距离”。 如果右边的儿子是空的，则距离为1，否则距离右边的儿子的距离为1。
一棵树满足以下条件(左偏性)。 每个节点右边儿子的距离小于或等于左边儿子的距离。 于是，一个nn个节点的靠左树的距离最大为log(n1(1(Lfloor ) log ) n1 )-1(Rfloorlog ) n1 ) 1。
合并操作时，每次合并低优先级的根节点和高优先级的根节点的右边的儿子时递归进行，回溯时更换左右的儿子判断是否保持左倾性，以及是否更新距离即可。 由于操作次数只与右儿子方向的深度，即“距离”有关，因此一次的复杂度最大为o(O(logn ) o(logn ) o(logn ) o ) logn )。
核心代码——合并：
inlineboolCMP(inta，int b ) {return ab； (//比较函数inlinevoidupdate(intx ) ) /左偏性if ) t [ t ] x ].sn [0].dist [ t [ x ].sn [1].dis ] swap ) t [ x.sn }inlineintmerg(intx，int y ) if (！ x |！ y ) return x^y； if(CMP(t[x].val，t[y].val ) ) swap(x ) x，y )； t[x].sn[1]=merg(t[x].sn[1]，y )； 更新(x； 返回x； }插入节点后，只需将其合并为单个堆即可。
删除节点时，如果节点是根，就直接合并左右子树即可。 否则很麻烦，需要将左右子树合并后，连接到父亲的节点，并向上更新以保持左偏性。
请注意，左对齐树不保证平衡，因此最大深度大于log级别，并且从一点到根遍历将导致超时。 但是，如果从某点向上更新而不动，可以进行直接结束的优化。 此时，由于遍历的长度不超过最大的dis，所以删除点的总复杂度也为o(O(logn ) o(logn ) o(logn ) logn ) )。
因为每次操作都是严格的o(log )
n ) O(log n) O(logn)，所以可以进行可持久化。 斜堆合并操作和左偏树非常相似，然而比左偏树还要简单。每次合并到右儿子后，直接无脑交换左右儿子即可。
inline bool cmp(int a,int b){return a>b;}inline int merg(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);t[x].sn[1]=merg(t[x].sn[1],y);swap(t[x].sn[0],t[x].sn[1]);return x;}赞美太阳！ 这时间不会被卡吗？
不会。这个合并的复杂度是均摊 O ( n log n ) O(nlog n) O(nlogn) 的。复杂度分析可以看这里。
合并的复杂度是对的，删除根节点的复杂度是对的，但是我不知道删除任意点的时候是否可以直接删。
另外，这个复杂度是均摊的，所以如果整一些奇怪操作可能会破坏均摊复杂度（比如可持久化，重复某一个历史操作），所以斜堆 应 该 是不能可持久化的。
随机堆我自己yy的一个可并堆的打法。
我们知道普通的暴力堆合并最坏是 O ( n ) O(n) O(n) 的，因为如果一直往左儿子或右儿子合并可能会出现很长的一条链。
回忆一下平衡树是怎么解决这个问题的：随机！
具体地，我们每次合并两个根时，如果在上面的根有一个儿子是空的，那么就合并到空的儿子那儿，否则随机往左儿子或右儿子方向合并。
inline bool cmp(ll a,ll b){return a>b;}inline int mergh(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);bool o=rand()%2;if(!t[x].sn[o^1])o^=1;t[x].sn[o]=mergh(t[x].sn[o],y);return x;}随机过后，给普通堆合并带来哪些变化呢？经过测试，堆的最大深度的期望并没有达到期望的 log n log n logn 级别，但是合并、插入、删除操作单次的期望复杂度都是 O ( log n ) O(log n) O(logn) 的。
就拿合并来说，由于算法遇到儿子数<2的节点就直接合并一次返回了，所以主要都是在左右儿子不为空的节点上遍历。随机访问情况下，这种节点显然最多遍历 O ( log n ) O(log n) O(logn) 个。
删除任意节点的时候，只需要合并左右子树然后接到父亲上即可，不需要像左偏树那样往上维护什么左偏性。因为通过上面的分析我们知道，合并的复杂度与树的形态无关。
另外，随机堆也可以实现可持久化。由于每次合并复杂度是均匀的，不会出现斜堆的那种均摊被卡的情况。而且由于不维护距离、不交换左右子树，它的可持久化 应 该 比左偏树好打一些。
附上可持久化的代码（仅多了1行）：
inline bool cmp(ll a,ll b){return a>b;}inline int mergh(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);int o=rand()%2;if(!t[x].sn[o^1])o^=1;int res=++IN;t[res]=t[x];t[res].sn[o]=mergh(t[x].sn[o],y);return res;}可见，除了常数大一点，随机堆其实和左偏树一样万能。
update2021.10.4:
最近学了一下C++11里面的新随机数，发现同为 O ( 1 ) O(1) O(1) 随机数，新旧常数的差别却非常大。因为这个随机堆合并每次都要调用随机数，非常依赖它的速度，所以应该根据情况选用不同随机方法。
如果运行不开O2，那么最好用上面的经典rand随机；
开了O2的话，用忧心的书包旋转的随机数引擎可以快10~20倍：
（注意：不开O2的忧心的书包旋转会比rand慢很多）
顺便提一下：以time(0)作为随机数种子是最好的，但是在有的比赛或网站上面却是禁用的，
CCF官方曾经也声明过禁止使用这个，后来好像没有了限制，但又没有声明可以使用。所以在比赛和做题中用time(0)是有风险的。
怎么办呢？HandInDevil给出了祂的**大法：用新声明的整形变量的地址（*new(int)）作为随机的种子，同样可以使每次运行程序得到不同的结果！
C++ pb_ds库 binary heap tag好家伙，没想到C++11已经有现成的可并堆了。学NM直接用
详细介绍可以看暴躁的咖啡的《C++的pb_ds库在OI中的应用》：
其实手写的堆合并并不复杂，而且总是比封装的数据结构灵活一些。
反正我大多数情况都用的随机堆。