_WA自动机的blog

过期高中生。

左偏树

发表于 更新于 阅读次数： Valine：

左偏树是一种最常用的可并堆。它除了满足堆性质（即根节点是整个子树中key值最小或最大的节点）之外，还有另外一个性质：该树是左偏的。顾名思义，对于每一个节点u，若既有左儿子ls又有右儿子rs，定义其“高度”\(\text{dis}(u)\)为到最近的叶子的距离，则\(\text{dis}(ls)\geq \text{dis}(rs)\)。直观理解就是左子树更深。

\(\textbf{Theorem 1.0}\)：对于节点个数为\(n\)的左偏树，其高度为\(\Theta(\lg n)\)。

  • \(\textbf{Proof}\)：对于一棵\(\text{dis}(u)=\text{h}\)的左偏树，节点最少时一定是满二叉树。即，对于左偏树，有：\(h \leq \log_2(n+1)\)

要实现左偏树，节点要记录以下信息：

1
2
3
4
struct Node
{
    int val,rt,ls,rs,dis;
}S[N];

左偏树最重要的操作（其实就是唯一的操作）是merge.下面实现函数\(\text{merge}(u,v)\)，功能为把u和v两棵左偏树（以下不区分节点和节点所代表的子树）合并，返回新树的根。

1
2
3
4
5
6
7
8
9
10
inline int Merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (S[x].val>S[y].val || (S[x].val==S[y].val && x>y)) swap(x,y); //保证x是最小的那个节点。
    S[x].rs=Merge(S[x].rs,y); //新树的根应为x。
    if (S[S[x].ls].dis<S[S[x].rs].dis) swap(S[x].ls,S[x].rs); //若右子树更深，交换左右子树，保持左偏性质
    S[S[x].ls].rt=S[S[x].rs].rt=x;
    S[x].dis=S[S[x].rs].dis+1;
    return x;
}

弹出堆顶元素时，记得要给堆顶节点的根重新赋值。因为如果不赋值的话，访问这个被删除元素并判断和其他节点连通性的时候会出现问题。\(\text{rt}(u)\neq \text{rt}(v)\)，判断错误。

完整代码如下（洛谷模板题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cassert>
#include <algorithm>

const int N=1e5+1000;

struct Node
{
    int val,rt,ls,rs,dis;
}S[N];

inline void swap(int &x,int &y){x^=y^=x^=y;}
inline int find(int x){return x==S[x].rt?x:S[x].rt=find(S[x].rt);}

inline int Merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (S[x].val>S[y].val || (S[x].val==S[y].val && x>y)) swap(x,y);
    S[x].rs=Merge(S[x].rs,y);
    if (S[S[x].ls].dis<S[S[x].rs].dis) swap(S[x].ls,S[x].rs);
    S[S[x].ls].rt=S[S[x].rs].rt=x;
    S[x].dis=S[S[x].rs].dis+1;
    return x;
}

inline void merge(int x,int y)
{
    if (S[x].val==-1 || S[y].val==-1) return;
    int u=find(x),v=find(y);
    if (u^v) S[u].rt=S[v].rt=Merge(u,v);
}

inline void poprt(int x)
{
    if (S[x].val==-1) return void(puts("-1"));
    x=find(x);
    printf("%d\n",S[x].val);
    S[x].val=-1;S[S[x].ls].rt=S[x].ls;S[S[x].rs].rt=S[x].rs;S[x].rt=Merge(S[x].ls,S[x].rs);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);S[0].dis=-1;
    for  (int i=1;i<=n;++i) scanf("%d",&S[i].val),S[i].rt=i;
    for (int i=1;i<=m;++i)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if (opt&1)
        {
            scanf("%d%d",&x,&y);
            merge(x,y);
        }
        else
        {
            scanf("%d",&x);
            poprt(x);
        }
    }
    // assert(0);
}