左偏树(可并堆)
左偏树与配对堆一样，是一种可并堆，具有堆的性质，并且可以快速合并。一种\(O(\log_2n)\)内合并的数据结构。
左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的 
\(dist\) 都大于等于右儿子的 \(dist\)。
定义
外节点：左儿子或右儿子为空的节点
距离：一个结点 \(x\) 的距离 \(dist_x\) 定义为其子树中与结点 \(x\) 最近的外结点到 \(x\) 的距离。特别地，定义空结点的距离为 \(-1\) 。
性质
左偏：左偏树每个节点的 \(dist\) 都等于其右儿子的 \(dist\) 加一。
堆：满足小根堆性质。
操作
合并
merge(x,y)：合并两棵以 \(x,y\) 为根的左偏树，返回合并之后的根节点。
- 若\(val_x<val_y\)，以 \(x\) 为合并后的根节点。
- 将 \(y\) 与 \(x\) 的其中一个儿子合并，合并后的根节点代替与 \(y\) 合并的儿子的位置，返回 \(x\)。
- 重复。若 \(x,y\) 中有一个为空节点，返回 \(x+y\)。
复杂度\(O(h)\)。进行优化：
由于左偏树中左儿子的距离大于右儿子的距离，每次将 \(y\) 与 \(x\) 的右儿子进行合并。
合并完成之后，判断节点 \(x\) 是否有 \(dist_{lc}>dist_{rc}\)，若没有则交换左右儿子并维护 \(x\) 的距离 \(dist_{lc}=dist_{rc}+1\)。
插入
新建节点，与左偏树合并
\(Min\)
根节点。
删\(Min\)
删根节点，合并左右儿子。
求给定节点所在左偏树的根节点
记录父亲节点，暴力跳。
使用并查集，并路径压缩。
\(\Large Code\)
#include<bits/stdc++.h>
#define cs const
#define ri register
using namespace std;typedef int I;const I inf=0x3f3f3f3f;typedef long long LL;I FL,CH;template<typename T>bool in(T&a){for(FL=1;!isdigit(CH)&&CH!=EOF;CH=getchar())if(CH=='-')FL=-1;for(a=0;isdigit(CH);CH=getchar())a=a*10+CH-'0';return a*=FL,CH==EOF?0:1;}template<typename T,typename...Args>I in(T&a,Args&...args){return in(a)+in(args...);}
cs int N=1e5+7;
int n,m,ls[N],rs[N],dist[N],rt[N];
bool mk[N];
struct node{
int id,v;
bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}
}t[N];
int Find(cs 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(t[y]<t[x]) swap(x,y);
rs[x]=Merge(rs[x],y);
if(dist[ls[x]]<dist[rs[x]]) swap(ls[x],rs[x]);
return dist[x]=dist[rs[x]]+1,x;
}
int main()
{
dist[0]=-1,in(n,m);
for(ri int i=1;i<=n;++i) in(t[i].v),rt[i]=t[i].id=i;
while(m--)
{
int op,x,y; in(op,x);
if(op==1)
{
in(y); if(mk[x]||mk[y]) continue;
x=Find(x),y=Find(y);
if(x!=y) rt[x]=rt[y]=Merge(x,y);
}
else
{
if(mk[x]) {puts("-1"); continue; }
x=Find(x),printf("%d\n",t[x].v),mk[x]=1;
rt[x]=rt[ls[x]]=rt[rs[x]]=Merge(ls[x],rs[x]);
ls[x]=rs[x]=dist[x]=0;
}
}
return 0;
}
标签：CH,dist,合并,儿子,节点,左偏 From： https://www.cnblogs.com/Bertidurlah/p/17181697.html