左偏树(可并堆)

左偏树

左偏树,其实也就是向左偏的树,左子树的深度大于右子树的深度,比如说下图:

这就是一棵左偏树,效率和堆差不多,唯一的区别就是,可以log(n)复杂度合并。

假如当前我们合并x,y两棵子树,我们就根据当前点的大小,然后将大的插入小的子树的右儿子,然后如果右儿子深度教深,那么就交换两棵子树。

我们怎么证明复杂度呢?

我们知道,合并与左儿子无关,然后右儿子的深度不会超过左儿子,设右儿子的深度等于左儿子,这样子是最坏情况,然而右儿子只有log(n)个,所以复杂度是log(n)的。

下面贴上代码 例题

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[100005];
int fa[100005],Son[100005][2],Siz[100005];
int get(int x){while(fa[x]) x=fa[x];return x;}//并查集,没有写路径压缩
int merge(int x,int y){//合并
    if(x==0||y==0) return x+y;
    if(a[x]>a[y]||(a[x]==a[y]&&x>y)) swap(x,y);//y连到x的左子树上
    Son[x][1]=merge(Son[x][1],y);fa[Son[x][1]]=x;//继续合并
    if(Siz[Son[x][0]]<Siz[Son[x][1]]) swap(Son[x][0],Son[x][1]);//交换左右儿子
    Siz[x]=Siz[Son[x][1]]+1;
    return x;
}
void pop(int x){a[x]=-1;fa[Son[x][0]]=fa[Son[x][1]]=0;merge(Son[x][0],Son[x][1]);}//删除
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,opt,x,y;i<=m;i++){
        if(scanf("%d",&opt),opt==1){
            scanf("%d%d",&x,&y);
            if(a[x]==-1||a[y]==-1) continue;
            int fx=get(x),fy=get(y);
            if(fx==fy) continue;
            merge(fx,fy);
        }else{
            scanf("%d",&x);
            if(a[x]==-1){printf("-1\n");continue;}
            int fx=get(x);
            printf("%d\n",a[fx]);
            pop(fx);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部