左偏树小结

1 左偏树的定义和性质

左偏树是一种优先队列,它除了支持优先队列的三个操作:插入,取得最小(最大)节点,删除最小(最大)节点之外,还支持一个额外的操作:合并操作

左偏树是一种可并堆,它以一棵二叉树的形式存在.二叉树中每一个节点保存有左右儿子(lc,rc)$(lc,rc)$,值(key)$(key)$,距离(dis)$(dis)$
在这里的节点i$i$的距离指的是节点i$i$到他的后代中,最近的叶子节点的距离

性质1:节点i$i$的值小于等于节点lc[i],rc[i]$lc[i],rc[i]$的值
这也就是一般二叉堆所满足的性质,被称为堆性质

性质2:节点lc[i]$lc[i]$的距离大于等于节点rc[i]$rc[i]$的距离
这就是左偏树所特有的性质,被称为左偏性质

性质1,性质2是构成左偏树的基本性质,属于定义类

性质3:节点i$i$的距离为节点rc[i]$rc[i]$的距离+1
这个性质是由性质2推出,方便我们在之后的操作中维护节点的距离

2 左偏树的操作

2.1 左偏树的合并

merge$merge$操作用来合并两棵左偏树,返回合并后新的左偏树,包含原有左偏树的所有元素
一棵左偏树我们通常用其根节点指针表示

merge(x,y)$merge(x,y)$
若某棵树为空,则直接返回另一棵树即可

if(x==0 || y==0) return x+y;

若x,y$x,y$均非空,我们使x$x$的根节点小于y$y$的根节点(否则swap(x,y)$swap(x,y)$)

if(key[x]>key[y] || (key[x]==key[y] && x>y)) swap(x,y);

x$x$的根节点显然就是新树中最小的节点,我们将其看做新树的根节点
接下来就只需要合并rc[x]$rc[x]$和y$y$

ch[x][1]=merge(ch[x][1],y);
f[ch[x][1]]=x;

在合并了rc[x]$rc[x]$和y$y$后,rc[x]$rc[x]$的距离可能变大,从而超过lc[x]$lc[x]$的距离
在这种情况下,交换lc[x],rc[x]$lc[x],rc[x]$即可

if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][1],ch[x][1]);

同时,更新x$x$的距离

dis[x]=dis[ch[x][1]]+1;

最后,返回新树,即x$x$

return x;

完整合并如下

int merge(int x,int y) {
    if(x==0 || y==0) return x+y;
    if(key[x]>key[y] || (key[x]==key[y] && x>y)) swap(x,y);
    ch[x][1]=merge(ch[x][1],y);
    f[ch[x][1]]=x;
    if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][1],ch[x][1]);
    dis[x]=dis[ch[x][1]]+1;
    return x;
}

时间复杂度为O(log2Node(x)+log2Node(y))$O(lo{g}_{2}Node(x)+lo{g}_{2}Node(y))$

2.2 左偏树的插入

显然,单个节点就是一颗左偏树
那么将插入看做两个左偏树合并即可

2.3 左偏树的删除

删除指的是删除左偏树中最大(最小)节点
通过性质1发现,左偏树的最大(最小)节点为其根节点
在删除根节点后,合并左右子树即可

void pop(int x) {
    key[x]=-1;
    f[ch[x][0]]=ch[x][0];
    f[ch[x][1]]=ch[x][1];
    merge(ch[x][0],ch[x][1]);
}

2.4 删除某个特定值的节点

在这里提供一个简单的方法
因为左偏树内部的节点是无序的,只有其根节点体现其有序性(最大(最小))
那么建立一个删除堆,将需要删除的值插入,若删除堆的根节点劫左偏树的根节点相同,则弹出两者根节点即可

3 例题

Luogu P3377 【模板】左偏树（可并堆）

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dis[N],ch[N][2],f[N],key[N],n,m;
int read() {
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') {flag=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {ans=ans*10+ch-'0';ch=getchar();}
    return ans*flag;
}
int merge(int x,int y) {
    if(x==0 || y==0) return x+y;
    if(key[x]>key[y] || (key[x]==key[y] && x>y)) swap(x,y);
    ch[x][1]=merge(ch[x][1],y);
    f[ch[x][1]]=x;
    if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][1],ch[x][1]);
    dis[x]=dis[ch[x][1]]+1;
    return x;
}
void pop(int x) {
    key[x]=-1;
    f[ch[x][0]]=ch[x][0];
    f[ch[x][1]]=ch[x][1];
    merge(ch[x][0],ch[x][1]);
}
int find(int x) {
    while(x!=f[x]) {x=f[x];}
    return x;
}
int main() {
    n=read();m=read();
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=n;++i) {key[i]=read();f[i]=i;dis[i]=0;}
    for(int i=1;i<=m;++i) {
        int cpt=read();
        if(cpt==1) {
            int x=read(),y=read();
            if(key[x]==-1 || key[y]==-1 || x==y) continue;
            x=find(x);y=find(y);
            if(x==y) continue;
            merge(x,y);
        }
        else {
            int x=read();
            if(key[x]==-1) {puts("-1");continue;}
            x=find(x);
            printf("%d\n",key[x]);
            pop(x);
        }
    }
    return 0;
}