发现以前学的时候摸鱼，都没有搞明白原理，现在来捡了。

左偏树是一种可并堆，满足以下性质:

  • 堆的性质：根的值比儿子大
  • 左偏性质：左子树的距离不小于右子树的距离

距离是什么意思？就是指当前节点到最近的外节点的距离。

外节点是什么？就是不完整的节点，也就是儿子个数不满的节点。

堆的性质决定了左偏树的作用，而左偏性质则保证了复杂度。

先考虑如何处理距离。因为一个节点的儿子如果不满，为保证左偏性质，那么不管怎么样它的右儿子一定是空的，也就是0，那么我们把0号节点的距离值赋值为-1，这样外节点的距离就是0，考虑用右儿子距离+1更新节点，这个过程我们在递归回溯实现即可（融入到合并的递归中）。

合并操作

左偏树的核心操作，不难，我们看着代码讲。

inline void Swap(int &x,int &y){
	int tmp=x;x=y;y=tmp;
}
int merge(int x,int y){
	if(!x||!y) return x|y;//树合并基操，有一个空子树就返回不空的
	if(t[x].val<t[y].val) Swap(x,y);//根据维护信息而定，保证了根的性质，这里是大顶堆
	rc(x)=merge(rc(x),y);//递归合并，因为左偏性质保证外节点的右子树为空
	if(t[rc(x)].d>t[lc(x)].d) Swap(lc(x),rc(x));//保证左偏性质
	fa(x)=fa(rc(x))=fa(lc(x))=x;//更新父亲关系
   //很多模板只更新右儿子的父亲，所以合并的时候需要另外更新两棵合并子树的父亲
	t[x].d=t[rc(x)].d+1;//计算距离，空子树距离返回-1
	return x;
}

查询堆顶

就是并查集啦。(可以使用路径压缩，因为只是破坏了并查集树的形态，不会破坏原树形态)

int find(int x){
	return x==fa(x)?x:fa(x)=find(fa(x));
}

删除堆顶

直接给堆顶打上删除标记，然后断开父亲关系，然后把堆顶的左右儿子合并，并且把堆顶的父亲指向这个合并出来的节点。（因为需要连通路径压缩）

void pop(int x){
	t[x].val=-1;
	fa(rc(x))=rc(x);fa(lc(x))=lc(x);
	t[x].fa=merge(lc(x),rc(x));
}

完整代码

挺好写的，不难理解。

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 200010
struct llt{
	int val,lc,rc;
	int fa,d;
}t[N];
#define fa(x) t[x].fa
#define lc(x) t[x].lc
#define rc(x) t[x].rc
int find(int x){
	return x==fa(x)?x:fa(x)=find(fa(x));
}
inline void Swap(int &x,int &y){
	int tmp=x;x=y;y=tmp;
}
int merge(int x,int y){
	if(!x||!y) return x|y;
	if(t[x].val>t[y].val||(t[x].val==t[y].val&&x>y)) Swap(x,y);
	rc(x)=merge(rc(x),y);
	if(t[rc(x)].d>t[lc(x)].d) Swap(lc(x),rc(x));
	fa(x)=fa(lc(x))=fa(rc(x))=x; 
	t[x].d=t[rc(x)].d+1;
	return x;
}
void pop(int x){
	t[x].val=-1;
	fa(rc(x))=rc(x);fa(lc(x))=lc(x);
	t[x].fa=merge(lc(x),rc(x));
}
int n,m; 
int main(){
	scanf("%d%d",&n,&m);
	t[0].d=-1;
	for(int i=1;i<=n;++i){
		int x;scanf("%d",&x);
		t[i].val=x;t[i].fa=i;
	}
	while(m--){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int x,y;
			scanf("%d%d",&x,&y);
			int xx=find(x),yy=find(y);
			if(t[x].val==-1||t[y].val==-1) continue;
			if(xx==yy) continue;
			merge(xx,yy);
		}
		if(opt==2){
			int x;scanf("%d",&x);
			int xx=find(x);
			if(t[x].val==-1) printf("%d\n",-1);
			else{
				printf("%d\n",t[xx].val);
				pop(xx);
			}
		}
	}
	return 0;
}