左偏树(可并堆)

左偏树(可并堆)

定义

在这之前,我们先来阐述一些定义:

  1. 外节点:\(ls\)\(rs\) 为空的节点
  2. 距离:节点的距离 \(dist_x\) 定义为节点 \(x\) 到距 \(x\) 最近的外节点的距离,空节点的距离为 \(-1\)

其次是左偏树的性质:

  1. 左偏性:即满足 \(dist_{ls}>=dist_{rs}\)
  2. 堆性质:若满足小根堆,则满足 \(v_x<=v_{ls}\) , \(v_x<=v_{rs}\)

这引出了左偏树的一些结论:

  1. 节点 \(x\) 的距离为 \(dist_{rs}+1\) (由于左偏性)
  2. 距离为 \(n\) 的左偏树至少有 \(2^n-1\) 个节点,最少时,形态接近满二叉树
  3. \(n\) 的节点的左偏树的根节点距离是 \(O(log_2n)\)

接下来是左偏树支持的一些操作:

  1. 合并
  2. 插入给定值
  3. 求最小值
  4. 删除最小值
  5. 求指定节点在左偏树的根节点

详解

一.合并

\(merge(x,y)\) 为合并以 \(x\) , \(y\) 为根节点的两棵子树,返回值为合并后的根节点。

先考虑堆的合并:

  1. \(v_x<=v_y\) ,则以 \(x\) 做为合并后的根节点。(若有 \(v_x>v_y\)\(swap(x,y)\) )
  2. \(y\)\(x\) 的一个儿子合并,合并后的根节点代替与 \(y\) 合并的儿子的位置,返回 \(x\)
  3. 重复以上操作,直到 \(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;
}

热门相关:腹黑老公圈宠:逃妻抱回家   爆萌宠妃:邪帝,要抱抱   大文豪   灭世魔帝   帝少宠妻有点甜