左偏树(左偏堆)

发表于 | 分类于 ，

什么是左偏树(堆):

左偏树是一种比较常用的可并二叉堆. 支持在最坏$O(log\ n)$的时间复杂度内进行堆的合并操作.

相关定义:

外结点: 左儿子或右儿子为空的结点.

距离: 一个结点到离它最近的外结点的距离. 特殊地, 外结点本身距离为0, 空结点距离为-1.

左偏树的性质及结论:

  1. 左偏树满足堆性质.

  2. 左偏树满足左偏性质, 即对于每个结点, 其左子结点距离$d_{ls}$大于等于右子结点距离$d_{rs}$.

  3. 由2, 结点$x$的距离$d_x = d_{rs} + 1$.

  4. 根结点距离为$d$的左偏树最少有$2^{n+1}-1$个结点, 此时该树为一个满二叉树.

  5. 同4, $n$个结点的左偏树距离最大为$log_2n$.

基本操作:

左偏树最基本操作便是合并操作.

定义函数merge(x,y), 作用是将根为$x, y$的两个堆合并, 返回合并后堆的根.

以小根堆为例, 基本步骤如下:

  1. 若$x,y$其中有一个结点为空结点, 则返回另一个结点. 否则下一步
  2. 若$v_x<v_y$, 则以$x$作为合并后的根结点, 否则以$y$作为根结点. 为避免讨论, 当$v_x \geq v_y$时, 直接交换$x,y$.
  3. 将$y$与$x$的左儿子进行合并, 即$ls_x=merge(ls_x,y)$.
  4. 合并完成后维护左偏性质: 当$d_{ls}<d_{rs}$时交换左右儿子.

示例代码如下所示: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//sn[x][0]为左儿子, sn[x][1]为右儿子
int merge(int i,int j) {
    if(i==0) {
        return j;
    }
    if(j==0) {
        return i;
    }
    if(a[i]>a[j] || (a[i]==a[j] && i>j)) {
        swap(i,j);
    }
    sn[i][1] = merge(j,sn[i][1]);
    fa[sn[i][1]] = i;
    if(d[sn[i][0]]<d[sn[i][1]]) {
        swap(sn[i][0],sn[i][1]);
    }
    d[i] = d[sn[i][1]] + 1;
    return i;
}

其他操作:

插入: 将插入结点当作左偏堆合并即可.

删除: 将根的左右子结点合并即可.

寻找所在堆的根结点: 直接沿着父结点向上寻找.

路径压缩优化找根:

类似于并查集, 每个结点记录一个值$rt$, 在递归找根时顺便压缩$rt$.

需要注意的是删除根节点$x$时可能有部分结点$rt = x$, 此时要将$rt_x$指向左右子结点合并后的新根.

作用:

左偏树由于具有合并和找根的功能, 可以算作是并查集的”进化版”.

同时由于具有权值, 可以用于树上的合并之中.

例题:

(luogu3377)【模板】左偏树（可并堆）

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cctype>
const int Mn(100500);
inline void swap(int& x,int& y) {   //交换
    x ^= y ^= x ^= y;
}
void qrd(int& x) {  //快读
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}
int a[Mn];  //权值
int fa[Mn], sn[Mn][2];  //根结点, 左右子结点
int d[Mn];  //距离
bool isd[Mn];   //是否被删除
int merge(int i,int j) {    //合并
    if(i==0) {
        return j;
    }
    if(j==0) {
        return i;
    }
    if(a[i]>a[j] || (a[i]==a[j] && i>j)) {
        swap(i,j);
    }
    sn[i][1] = merge(j,sn[i][1]);
    fa[sn[i][1]] = i;
    if(d[sn[i][0]]<d[sn[i][1]]) {
        swap(sn[i][0],sn[i][1]);
    }
    d[i] = d[sn[i][1]] + 1;
    return i;
}
int find(int x) {   //找根(用到了路径压缩)
    return fa[x] == 0 ? x : fa[x] = find(fa[x]);
}

int main() {
    int n,m;
    qrd(n), qrd(m);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
    }
    while(m--) {
        int o;
        qrd(o);
        if(o==1) {
            int x,y;
            qrd(x), qrd(y);
            if(!isd[x]&&!isd[y]) {
                int rx = find(x);
                int ry = find(y);
                if(rx!=ry) {    //只有当两个数不在同一堆里才合并
                    merge(rx,ry);
                }
            }
        } else {
            int x;
            qrd(x);
            if(isd[x]) {
                printf("-1\n");
            } else {
                int rx = find(x);
                printf("%d\n",a[rx]);
                isd[rx] = true;
                fa[sn[rx][0]] = fa[sn[rx][1]] = 0;
                fa[rx] = merge(sn[rx][0],sn[rx][1]);    //将rx的根指向合并后的新根
            }
        }
    }
    return 0;
}