左偏树是一种可以合并的“堆”。这里打了引号，是因为左偏树并不是堆，但是能完成与堆类似的功能。而且还能支持可持久化。
在可合并对中，左偏树是最常用的。虽然它的效率不及斐波那契堆与配对堆，但是复杂度是同一个级别，单次操作最坏情况下都是\(O(log_2n)\)的。而且不像斐波那契堆，码量大，难理解，在竞赛中用太不合算了，配对堆不资瓷可持久化。。。。。
放张表格，看看你打算学哪种？这里（目前）只教左偏树。其他的除了二叉堆博主都不会
| 指标 | 二叉堆 | 左偏树/斜堆 | 二项堆 | 斐波那契堆 | 配对堆 |
|---|---|---|---|---|---|
| 建堆 | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
| 插入节点 | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) | \(O(1)\) | \(O(1)\) |
| 取最值节点 | \(O(1)\) | \(O(1)\) | \(O(log_2n)\) | \(O(1)\) | \(O(1)\) |
| 删除最值节点 | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) |
| 删除任意已知节点 | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) |
| 合并 | \(O(nlog_2n)\) | \(O(log_2n)\) | \(O(log_2n)\) | \(O(1)\) | \(O(1)\) |
| 空间 | \(--\) | \(-\) | \(+\) | \(++\) | \(-\) |
| 代码复杂度 | \(--\) | \(-\) | \(++\) | \(+++\) | \(-\) |
- 已知：表示知道编号，而不是值。
- \(--\)表示很小，\(-\)表示较小，\(+\)表示一般，\(++\)表示较大，\(+++\)表示很大。
左偏树的基本结构与堆有许多相似之处。它是一棵二叉树，对于一个节点\(x\)，设其左儿子为\(ls\)，右儿子为\(rs\)，值为\(v_x\)总是满足\(v_x \le v_{ls},v_x\le v_{rs}\)（如果存在左右儿子）。
再次明确一遍，左偏树不是堆，它不一定是完全二叉树。“左偏”的意义就在于保证时间复杂度（否则一条链就能把复杂度卡到\(O(n^2)\)）。来看看何为“左偏”。
先讲一讲外节点。如果一个节点没有左儿子或没有右儿子（或者都没有），那么这个节点被称为外节点。我们设\(dis_{x}\)表示\(x\)与最近的外节点之间的距离。（一条边的长度为1）。特别地，空节点0的\(dis\)为\(-1\)。（这样就可以自然地完成外节点的\(dis\)为0）
左偏即为对于任意节点\(x\)，满足\(dis_{ls}\ge dis_{rs}\)。（这样就可以得到\(dis_x=dis_{rs}+1\)）
为什么这样就可以保证复杂度呢？
很明显，一般地，节点总是集中于左子树，我们就可以把操作集中于右子树来减少操作。
来看看更严谨的证明。
- 引理：最大dis为k的左偏树节点个数至少为\(2^{k+1}-1\)（满二叉树）。
我们运用反证法。我们将深度大于k的节点去除，得到树T，如果树T不是满二叉树，则树T中必定有一个外节点\(x\)深度小于k，与根节点dis为k矛盾，原命题成立。
- 定理： 由对于一个有\(n\)个节点的左偏树，最大距离不超过 \(\log_2(n+1)-1\)证明： 设 \(max\{dist\}=k\) ，由引理得\(n\geq 2^{k+1}-1\) ，移项得： \(k\leq \log_2(n+1)-1\) 。
这就保证了\(O(log_2n)\)的复杂度。
如何实现
合并
合并操作与FHQ Treap十分类似，如果你会FHQ Treap，这将很好理解。
int Merge( int x, int y ){ if ( !x || !y ){ return x | y; }//如果有一个堆为0，直接返回这个堆 if ( val[x] > val[y] || ( val[x] == val[y] && x > y ) ) swap( x, y );//使x的值小于y(将x做为根节点) R[x] = Merge( R[x], y ); fa[R[x]] = x;//R[x]可能已被更改，更新R[x]的父亲 if ( dis[L[x]] < dis[R[x]] ) swap( L[x], R[x] );//维持左偏性质 dis[x] = dis[R[x]] + 1;//更新dis return x; } val[x]记录该节点保存的值，L[x]表示\(x\)的左儿子（没有的话就为0），R[x]表示\(x\)的右儿子（没有的话就为0）。fa[x]记录该节点的父亲。
Merge的作用就是将两个堆（已知根节点）合并成一个并返回其根节点。由于要保持堆的性质，根节点的值肯定要是最小的。要合并的两个堆中，值最小的肯定是\(x\)与\(y\)，如果\(y\)的值比\(x\)小，那\(x\)肯定不能作为根节点，所以这时候\(x\)不能作为根节点，只能把\(y\)作为根节点了。为了方便处理，我们直接交换x与y（注意：不是val，交换的是两个堆的位置）。这样\(x\)就肯定为根节点了。我们不改变\(x\)的左子树（因为是左偏的嘛，左子树太费时），将原来\(x\)的右子树与\(y\)合并作为\(x\)的右子树。注意要更新\(dis\)与\(fa\)的值。
还有一个前面提到过的小细节：dis[0]在主程序中必须赋为-1
删除
删除根节点操作就更简单了，直接合并左右儿子即可。
#define Del(x) val[x] = -1, fa[L[x]] = fa[R[x]] = 0, Merge( L[x], R[x] )//注意先把父亲赋为0
会了这两个操作，就可以完成啦。。。
#includeusing namespace std;#define MAXN 100005int N, M;int L[MAXN], R[MAXN];int fa[MAXN], val[MAXN], dis[MAXN];int Merge( int x, int y ){ if ( !x || !y ){ return x | y; } if ( val[x] > val[y] || ( val[x] == val[y] && x > y ) ) swap( x, y ); R[x] = Merge( R[x], y ); fa[R[x]] = x; if ( dis[L[x]] < dis[R[x]] ) swap( L[x], R[x] ); dis[x] = dis[R[x]] + 1; return x; }#define Del(x) val[x] = -1, fa[L[x]] = fa[R[x]] = 0, Merge( L[x], R[x] )int find( int x ){ while( fa[x] ) x = fa[x]; return x;}//fa表示直接父亲！这不是并查集！不要想着去路径压缩！int main(){ scanf( "%d%d", &N, &M ); for ( int i = 1; i <= N; ++i ) scanf( "%d", &val[i] ); dis[0] = -1;//重要！ for ( int i = 1; i <= M; ++i ){ int opt, x, y; scanf( "%d", &opt ); if ( opt == 1 ){ scanf( "%d%d", &x, &y ); if ( val[x] == -1 || val[y] == -1 ) continue;//有一个点被删除就不要操作了 x = find(x); y = find(y);//记得先找到根节点再合并 if ( x != y ) Merge( x, y ); } else{ scanf( "%d", &x ); if ( val[x] == -1 ) printf( "-1\n" );//用val=-1标记已被删除的节点（输入全是正整数，如果有负数可以用INT_MIN，反正视数据范围而定） else printf( "%d\n", val[x = find(x)] ), Del(x); } } return 0;}
当然，操作远远不止这些~慢慢更
修改
这题要修改值。。。其实暴力一点，直接删去，再合并就OK。。。
具体一点：
- 删去两个左偏树的根节点（用x、y保存编号，t1、t2保存删去x、y后的左偏树根节点编号）（删除方法同上）
val[x]与val[y]减半- 初始化x、y（
L[x]=R[x]=fa[x]=0，y也一样） - 合并x、y、t1、t2
- 返回
val[根节点]
不难理解吧？注意一个小优化，先合并x、y。因为x、y都只剩一个根节点，合并复杂度是\(O(1)\)的。这只是优化常数，不优化也能过。
核心代码：
int fight( int x, int y ){ x = find(x); y = find(y); if ( x == y ) return -1; fa[L[x]] = fa[R[x]] = fa[L[y]] = fa[R[y]] = 0; int t1, t2; t1 = Merge( L[x], R[x] ); t2 = Merge( L[y], R[y] ); val[x] >>= 1; val[y] >>= 1; L[x] = R[x] = L[y] = R[y] = dis[x] = dis[y] = 0; x = Merge( x, y ); x = Merge( x, t1 ); x = Merge( x, t2 ); return val[x];} 还有一个猥琐的坑点：多组数据！记得初始化。
更新中。。。。