左偏树(可并堆)
左偏树(可并堆)
定义
在这之前，我们先来阐述一些定义：
- 外节点：\(ls\) 或 \(rs\) 为空的节点
- 距离：节点的距离 \(dist_x\) 定义为节点 \(x\) 到距 \(x\) 最近的外节点的距离，空节点的距离为 \(-1\)
其次是左偏树的性质：
- 左偏性：即满足 \(dist_{ls}>=dist_{rs}\)
- 堆性质：若满足小根堆，则满足 \(v_x<=v_{ls}\) , \(v_x<=v_{rs}\)
这引出了左偏树的一些结论：
- 节点 \(x\) 的距离为 \(dist_{rs}+1\) (由于左偏性)
- 距离为 \(n\) 的左偏树至少有 \(2^n-1\) 个节点，最少时，形态接近满二叉树
- 有 \(n\) 的节点的左偏树的根节点距离是 \(O(log_2n)\)
接下来是左偏树支持的一些操作：
- 合并
- 插入给定值
- 求最小值
- 删除最小值
- 求指定节点在左偏树的根节点
详解
一.合并
\(merge(x,y)\) 为合并以 \(x\) , \(y\) 为根节点的两棵子树，返回值为合并后的根节点。
先考虑堆的合并：
- 若 \(v_x<=v_y\) ,则以 \(x\) 做为合并后的根节点。(若有 \(v_x>v_y\) 则 \(swap(x,y)\) )
- 将 \(y\) 与 \(x\) 的一个儿子合并，合并后的根节点代替与 \(y\) 合并的儿子的位置，返回 \(x\)
- 重复以上操作，直到 \(x\) 与 \(y\) 有一方是空节点。
然鹅，这样合并的操作复杂度为 \(O(h)\) \(h\) 为树高，当堆退化为链时，复杂度为 \(O(n)\) ,想要进一步优化，则要优化左偏树。由于在左偏树中，左儿子的距离大于右儿子的距离，所以每次选择右儿子进行合并，则单次复杂度可以来到 \(O(long_2n)\) ;
但两棵树合并后可能破坏左偏树的左偏性，故在每次合并后，判断节点 \(x\) 是否符合 \(dist_{ls}>=dist_{rs}\) ，若不满足则 \(swap(ls,rs)\) ,并维护 \(dist_x=dist_{rs}+1\) ,即可维护左偏树的左偏性。
二.插入给定值
新建一个值等于插入值的点，将该节点与左偏树合并即可。
三.求最小值
由于左偏树的堆性质，所以左偏树的最小值即为左偏树的根节点的值。
四.删除最小值
等价于删除左偏树的根节点，合并左右子树即可。
五.求指定节点在左偏树的根节点
可以记录每个节点的父亲节点，然后暴力跳父亲节点。
int find(int x){
if(rt[x]) return find(rt[x]);
return x;
}
是不是非常熟悉，当然，可以使用路径压缩优化。
int find(int x){
if(rt[x]) return rt[x]=find(fa[x]);
return x;
}
如此，我们便需维护 \(rt\) 数组。在合并两个节点时，令：
rt[x]=rt[y]=merge(x,y);
在删除左偏树的最小值时
rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);
因为 \(x\) 之前靠近根节点,在路径压缩时，\(rt\) 数组有可能等于 \(x\) ，所以 \(rt[x]\) 也指向删除后的根节点。
由于使用了路径压缩优化，导致 \(x\) 的树形结构被破坏，若之后还需使用 \(x\) 则需重建一个同值节点。使用路径压缩优化后，可以在 \(O(log_2n)\) 的时间复杂度内找到一个点在左偏树的根节点。
完整代码
#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 1e5+10;
int m,n,x,y,op;
int ls[maxn],rs[maxn],dist[maxn],rt[maxn];
bool tf[maxn];
struct node{ //点节点结构体
int id,v; //编号，价值
bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}
}v[maxn];
int find(int x){ //寻找祖宗
if(rt[x]==x)
return x;
return rt[x]=find(rt[x]); //路径压缩
}
int merge(int x,int y){ //合并x，y
if(!x||!y) //若这两个节点中存在空节点
return x+y;
if(v[y]<v[x]) //保证v[x]<v[y]
swap(x,y);
rs[x]=merge(rs[x],y); //由于左偏性质，最优合右树
if(dist[ls[x]]<dist[rs[x]]) //维护左偏性质
swap(ls[x],rs[x]);
dist[x]=dist[rs[x]]+1; //维护根节点距离
return x;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
dist[0]=-1;
cin>>n>>m;
seq(i,1,n){ //初始化
cin>>v[i].v; //输入价值
rt[i]=i;
v[i].id=i;
}
while(m--){
cin>>op>>x;
if(op==1){
cin>>y;
if(tf[x]||tf[y]) continue;
x=find(x);y=find(y);
if(x!=y) rt[x]=rt[y]=merge(x,y); //若不在一棵树上
}
else{
if(tf[x]){
cout<<"-1"<<"\n";
continue;
}
x=find(x);
cout<<v[x].v<<"\n";
tf[x]=true;
rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);
ls[x]=rs[x]=dist[x]=0;
}
}
return 0;
}