前言

关于我想去学环状树却学了左偏树这件事

正文

前置芝士

并查集

性质

根据算法名称就可以知道,这是一个森林中所包含的所有树都向左偏的森林(也是因为他向左偏,并且可以进行合并,所以他也是可并堆)。

算法函数

建树: 很简单,并查集实现(就不放代码了)。

合并: 也就是把两棵树合并先放代码:

int merge(int x,int y/*要进行合并的两棵树的根*/) {
    if (!x or !y) {
        return x+y;
    }
    if (val[x]>val[y] or (val[x]==val[y] and x>y)/*可以根据大小跟堆调整大小余号*/) {
        swap(x,y);//维护左偏
    }
    r[x]=merge(r[x],y);//递归寻找右子树
    fa[l[x]]=fa[r[x]]=fa[x]=x;
    if (dis[l[x]]<dis[r[x]]) {
        swap(l[x],r[x]);//依旧维护
    }
    dis[x]=dis[r[x]]+1;//更新根节点到叶子节点的最短路径
    return x;
}

按照代码从上往下说,首先来看这句:

if (!x or !y) {
    return x+y;
}

什么意思呢,很简单我们可以把它和 r[x]=merge(r[x],y); 结合食用,也就是说再找右子树时,如果到了叶子节点或 $y$ 变为 $0$ 了,就把以 $y$ 为根的树变为右子树或返回右子树当前节点的值(因为 $y$ 等于零的情况肯定是前几次循环,$x$ 与 $y$ 交换了值)。

其他就不用说了,都是维护左偏树。

删除: 删除分两种,一种是把根节点删除(也就是删除堆中的最大或最小元素),第二种是删除任意元素。

先上代码:

//删除堆顶
void Delete(int x) {
    vis[x]=1;
    fa[l[x]]=l[x],fa[r[x]]=r[x];
    fa[x]=merge(l[x],r[x]);
}
//任意
void Delete(int x) {
    int L=l[x],R=r[x];
    fa[L]=L,fa[R]=R;
    l[x]=r[x]=dis[x]=0;
    merge(merge(L,R),find(x));
}

其实这两种差不了多少,都是先把左右子树合并,再和自己父节点所在的子树合并(可以想一想,很简单)。

嗯对就没了,一共就这两种操作,上一下例题 p3377 的代码 (无注释):

#include <iostream>

using namespace std;
int n,m;
int val[1000001],fa[1000001];
int dis[1000001],vis[1000001];
int r[1000001],l[1000001];

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

int merge(int x,int y) {
    if (!x or !y) {
        return x+y;
    }
    if (val[x]>val[y] or (val[x]==val[y] and x>y)) {
        swap(x,y);
    }
    r[x]=merge(r[x],y);
    fa[l[x]]=fa[r[x]]=fa[x]=x;
    if (dis[l[x]]<dis[r[x]]) {
        swap(l[x],r[x]);
    }
    dis[x]=dis[r[x]]+1;
    return x;
}

void join(int x,int y) {
    int nx=find(x),ny=find(y);
    if (vis[x] or vis[y] or nx==ny) {
        return;
    }
    fa[nx]=fa[ny]=merge(nx,ny);
}

void Delete(int x) {
    vis[x]=1;
    fa[l[x]]=l[x],fa[r[x]]=r[x];
    fa[x]=merge(l[x],r[x]);
}

int get_ans(int x) {
    if (vis[x]) {
        return 0;
    }
    int nx=find(x);
    Delete(nx);
    return val[nx];
}

int main() {
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>val[i];
        fa[i]=i;
    }
    cin>>m;
    for (int i=1,x,y;i<=m;i++) {
        int tmp;
        cin>>tmp>>x;
        if (tmp==1) {
            cin>>y;
            join(x,y);
        } else if (tmp==2){
            cout<<get_ans(x)<<endl;
        }
    }
    return 0;
}

例题

p2713

和板子题一模一样。

p4971

需要删去任意节点,另外注意判断。

p1456

每次合并要除以 $2$,以及要寻找堆顶。

finally

没了。

分类: 文章

Evol_Yester_Nt

抽紫烟,吸纯氧,健康生活everyday

0 条评论

发表回复

Avatar placeholder

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