Chlience

【算法】左偏树小结
1 左偏树的定义和性质左偏树是一种可并堆,它以一棵二叉树的形式存在二叉树中每一个节点保存有左右儿子 $(ch[x]...
扫描右侧二维码阅读全文
28
2019/02

【算法】左偏树小结

1 左偏树的定义和性质

左偏树是一种可并堆,它以一棵二叉树的形式存在

二叉树中每一个节点保存有左右儿子 $(ch[x][0]ch[x][1])$ ,值 $(key)$ ,距离 $(dis)$

定义外节点为左子树或右子树为空的节点
这里所谓的距离 $(dis)$ 其实是指节点 $i$ 到它的后代中最近的外节点所经过的边数
如果当前点为外节点,那么其距离为 $0$

性质1:当前节点的值小于等于儿子的值
这也就是一般二叉堆所满足的性质,被称为堆性质

性质2:当前节点左儿子的距离大于等于右儿子 的距离
这就是左偏树所特有的性质,被称为左偏性质
也正是因为这条性质,整棵树处于一种“左重右轻”的状态,故称其为左偏树

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

性质3:当前节点的距离为右儿子的距离 $+1$
这个性质由性质2推出,方便我们在之后的操作中维护每个节点的距离

2 左偏树的操作

2.1 左偏树的合并

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

$merge(x,y)$

当前需要合并以 $x,y$ 为根的两棵左偏树

若某棵树为空,则直接返回另一棵树即可

否则,我们取两者根节点较小的一个,假设是 $x$ ,作为合并后新的根节点
接着递归合并 $x$ 的右儿子和 $y$

在合并了右儿子和 $y$ 后,右儿子的距离可能变大,从而超过左儿子
为了维护左偏性质,需要交换两个儿子

同时,更新$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;
}

由于合并操作一直都是在两棵左偏树的右链上进行的,所以合并次数不会超过右链的长度和

由左偏性质可得,若一棵左偏树根节点距离为 $k$ ,那么其点数最少为 $2^{k+1}-1$
那么一棵 $n$ 个节点的左偏树的根节点距离自然最多为 $\lfloor\log_2(n+1)\rfloor-1$,近似的认为是 $\log_2 n$

那么时间复杂度等于两条右链的总长度: $O(\log_2 |x|+ \log_2 |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;
}
Last modification:February 28th, 2019 at 04:49 pm

Leave a Comment