左偏树简介
左偏树是一种可并堆，也叫左偏堆、左倾堆、左氏堆，是一种树，具有堆的性质，可以实现快速合并。左偏树不是二叉搜索树，不是平衡树，因为它不满足中序有序性，无法进行二分搜索，因此不可以快速查找或者删除特定值的节点。
左偏树的性质
堆序性
节点的值大于或者等于（或小于等于）其左右子节点的值。对最大堆，父节点大，子节点小，每个结点的值都大于或者等于其左右子节点的值。
左偏性
左偏性指“向左偏”，节点的左子节点的距离大于 或等于右子节点的距离。左偏树的节点除了和二叉树结点一样有左右子树，还有两个属性：外界点和距离。
- 外节点：节点$i$的左子树或者右子树为空时，节点$i$被称为外节点。
- 距离：节点i的距离指节点$i$到他的后代中最近的外节点所经过的边数。特别地，若节点$i$自身是外节点，则它的距离为$0$；空节点的距离为$-1$（有些地方例如OI Wiki定义：自身是外节点的距离是$1$，空节点的距离是$0$。但是这样规定写代码不方便）。
左偏树有左偏性，每个节点的左子节点的距离都大于或者等于右子节点的距离。
需要注意的是，距离不是深度，左偏树的深度没有保证，一条向左的链也是左偏树。
节点的距离等于它的右子节点的距离加$1$
因为左偏性保证每个结点的左子节点的距离大于右子节点的距离，而节点的距离等于最近外节点的距离，因此节点的距离等于右子节点的距离加$1$。
$n$个结点的左偏树距离最多为$\log(n+1)-1$
假设$n$个结点的左偏树的距离为$d$，因为节点的距离等于它右子节点的距离加$1$，所以$d$实际上是从树根开始的最右侧通路长度。从树根到最近外节点的路径长度为$d$，从树根开始，高度为d的部分是一颗满二叉树，该满二叉树的节点总数为$2^{d+1}-1$。根据左偏性，该左偏树的左下侧还可能有其他节点，因此$n$个节点的左偏树至少包含$2^{d+1}-1$个节点。最终可以得出$d \le \log(n+1)-1$
左偏树的操作
核心操作：合并
假如当前有两棵左偏树，它们的根节点分别是$a,b$。
- 比较$a,b$的权值大小，如果$a$的权值大于$b$的权值，就交换两颗左偏树，保证最小堆的堆序性。
- 合并$a$的右子树与以$b$为根的左偏树，将合并后的左偏树作为$a$的右子树。在这一步需要进行递归，直到其中的一棵左偏树只剩下一个节点直接相接。
- 比较左右子树的距离，如果左子树的距离小于右子树的，就交换。然后更新$a$的距离为右子树的距离加$1$。
每一次递归合并时，总是分解出一棵树的右子树与另一颗树合并，在我们的合并过程中也许需要交换，所以合并树的复杂度时两颗树的距离之和，即合并一次的时间复杂度为$O(\log n_a+\log n_b)$
删除根节点
删除根结点时只需将左右子树的父节点修改为自己，然后合并两棵子树即可。
删除任意节点
先将左右儿子合并，然后自底向上更新距离，不满足左偏性质时交换左右儿子，当无需更新距离时结束递归。
整堆加上、减去一个值，乘上一个正数
在根打上标记，删除根或者合并堆或者访问儿子时下传标记。
插入节点
插入一个新节点，首先创建一棵只包含一个新节点的左偏树，然后和原树合并。
创建左偏树
创建左偏树有两种方法：
- 将每个节点依次插入，每次插入的时间复杂度为$O(\log n)$，总共的复杂度为$O(n\log n)$。
- 两两合并，将n个节点放入队列中，依次从队头取出两颗左偏树，合并后加入队尾，直到只剩下一棵左偏树，时间复杂度为$O(n)$
求节点所在左偏树的根节点
这里还有两种方法：
记下每个节点的父亲fa[]，然后暴力跳父亲节点。
int find(int x) { if(fa[x]) return find(fa[x]); return x; }并查集思想，采用路径压缩，求出左偏树的根节点。
int find(int x){ return rt[x]==x?x:rt[x]=find(rt[x]); }如果采取这种写法，需要维护$rt[x]$的值。在合并两个节点xy时，
rt[x]=rt[y]=merge(x,y)。在删除左偏树中的最小值时，令
rt[tree[x].lc]=rt[tree[x].rc]=rt[x]=merge(tree[x].lc,tree[x].rc因为x是之前左偏树的根节点，在路径压缩时可能有rt的值等于x，所以rt[x]也要指向删除后的根节点。这样时间复杂度被压缩到O(\log n)
代码
来源：洛谷：P3377 【模板】左偏树（可并堆）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long uLL;
typedef __int128 int128;
typedef unsigned __int128 uint128;
typedef long double Ld;
#define reg register;
#define space putchar(' ')
#define enter putchar('\n')
#define PI 3.14159265358979323846
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 1000010
// void gettime(){
// cerr<<"time:"<<(double)clock()<<"ms"<<endl;
// }
namespace Fast{
template<typename T>inline void read(T &x){
x=0;bool f=false;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=~x+1;
}
template<typename T>inline void print(T x){
int s[65],top=0;
if(x<0)putchar('-'),x=~x+1;
while(x)s[++top]=x%10,x/=10;
if(!top)s[++top]=0;
while(top)putchar(s[top--]+'0');
}
template<typename T,typename...Args>inline void read(T &x,Args&...others){
read(x),read(others...);
}
template<typename T,typename...Args>inline void print(T x,Args...others){
print(x),space,print(others...);
}
const double eps=1e-7;
template<typename T>inline T Abs(T x){return x>0?x:-x;}
template<typename T>inline T Max(T x,T y){return x>y?x:y;}
template<typename T>inline T Min(T x,T y){return x<y?x:y;}
template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
}
using namespace Fast;
int n,m,dis[M],rt[M];
bool vis[M];
struct Node{
int id,val,lc,rc;
bool operator < (const Node x)const{
return val==x.val?id<x.id:val<x.val;
}
}tree[M];
int find(int x){
return rt[x]==x?x:rt[x]=find(rt[x]);
}
int merge(int x,int y){
if(!x||!y)
return x|y;
if(tree[y]<tree[x])
swap(x,y);
tree[x].rc=merge(tree[x].rc,y);
if(dis[tree[x].lc]<dis[tree[x].rc])
swap(tree[x].lc,tree[x].rc);
dis[x]=dis[tree[x].rc]+1;
return x;
}
int main(){
dis[0]=-1;
read(n,m);
int x,y;
for(int i=1;i<=n;i++){
read(tree[i].val);
rt[i]=i;
tree[i].id=i;
}
for(int i=1;i<=m;i++){
int opt;
read(opt);
if(opt==1){
read(x,y);
if(vis[x]||vis[y])
continue;
x=find(x),y=find(y);
if(x!=y)
rt[x]=rt[y]=merge(x,y);
}
if(opt==2){
read(x);
if(vis[x]){
print(-1);
enter;
continue;
}
x=find(x);
print(tree[x].val);
enter;
vis[x]=1;
rt[tree[x].lc]=rt[tree[x].rc]=rt[x]=merge(tree[x].lc,tree[x].rc);
tree[x].lc=tree[x].rc=dis[x]=0;
}
}
return 0;
}
