左偏树,配对堆与可持久化可并堆

发表于 | 分类于 |

试图进行算法复健.jpg

预警:本文基本复制黏贴oiwiki,仅供个人学习使用

10.28_updated:请勿使用rs函数版本左偏树,在绝大部分编译环境下使用会发生错误

https://oi-wiki.org/ds/leftist-tree/

引入定义:

外节点:没有左儿子或右儿子的节点

空节点:没有左儿子和右儿子的节点

dist:外节点或空节点dist记为1,其他节点为到其子树中最近外节点的距离+1(故每个节点的dist=min{左节点dist,右节点dist}+1)

注意:若一个树的总数为n,则其root的dist最多不超过log[n+1]的下界

左偏树定义

左偏树为一颗二叉树,其满足堆的性质(即父节点大于子节点),且每个节点左儿子的dist都大于等于右儿子的dist,故每个节点的dist都为右节点dist+1(注意一条左链也是左偏树)

左偏树操作

以维护小根堆左偏树为例

merge操作

合并两个堆时,取较小的堆顶节点作为新堆顶,然后将该节点的左儿子保留为新堆根节点的左儿子,取其右儿子与另一个堆重复上述步骤,取合并后的堆作为新堆根节点的右儿子,合并后检查dist值并通过交换儿子维护.

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int merge(int x,int y)
{
    if(!x||!y) return x|y;
    if(t[x].val>t[y].val)
    {
        swap(x,y);
	}
    t[x].rs=merge(t[x].rs,y);
    if(t[t[x].rs].dist>t[t[x].ls].dist)
    {
        swap(t[x].rs,t[x].ls);
    }
    t[x].d=t[t[x].rs]+1;
    return x;
}

时间复杂度分析:由于每次merge操作,需要合并的两个堆中都会有一个堆根节点的dist-1,故最多执行log次merge操作

可以理解为锁死节点的dist为右节点的dist+1,然后通过每次保留左子树来达到启发式合并的类似效果?

插入操作

将单个节点视作堆,直接用merge就行

删除根节点

合并根节点的左右子树就行

删除任意节点

将欲删除节点的左右子树合并后,向上更新

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
//使用rs函数,免去交换子树的操作
//结构体添加fa,方便pushup
int& rs(int x)
{
    return t[x].ch[t[t[x].ch[1]].d<t[t[x].ch[0]].d];
}
int merge(int x,int y)
{
    if(!x||!y)
    {
        return x|y;
	}
    if(t[x].val>t[x].val)
    {
        swap(x,y);
    }
    rs(x)=merge(rs(x),y);
    t[rs(x)].fa=x;
    pushup(x);
    return x;
}
void pushup(int x)
{
    if(!x)
    {
        return;
    }
    if(t[x].d!=t[rs(x)].d+1)
    {
        t[x].d=t[rs(x)].d+1;
        pushup(t[x].fa);
    }
}

复杂度不变,仍是log级

注意使用rs()函数的代码可能会因为不同编译器的执行顺序出坑

为堆添加标记

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
void pushdown(int x)
{
    if(t[x].lazy)
    {
        if(t[x].ch[0])
        {
            t[t[x].ch[0]].lazy+=t[x].lazy;
            t[t[x].ch[0]].val+=t[x].lazy;
        }
        if(t[x].ch[1])
        {
            t[t[x].ch[1]].lazy+=t[x].lazy;
            t[t[x].ch[1]].val+=t[x].lazy;
        }
        t[x].lazy=0;
    }
}
void pushup(int x)
{
    if(!x)
    {
        return;
    }
    if(t[x].d!=t[rs(x)].d+1)
    {
        t[x].d=t[rs(x)].d+1;
        pushup(t[x].fa);
    }
}
int merge(int x, int y)
{
 	if(!x||!y)
    {
        return x|y;
	}
    if(t[x].val>t[x].val)
    {
        swap(x,y);
    }
    pushdown(x);
    rs(x)=merge(rs(x),y);
    t[rs(x)].fa=x;
    pushup(x);
    return x;
}
int pop(int x) {
  pushdown(x);
  return merge(t[x].ch[0], t[x].ch[1]);
}

随机合并

1
2
3
4
5
6
7
8
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[y].val < t[x].val) swap(x, y);
  if (rand() & 1)  // 随机选择是否交换左右子节点
    swap(t[x].ls, t[x].rs);
  t[x].ls = merge(t[x].ls, y);
  return x;
}

随机合并,平均复杂度仍为log且省去dist的相关计算

在某些左偏树被卡的情况相当快(比如:https://www.luogu.com.cn/problem/P3273)

配对堆

待补

可持久化可并堆

即在左偏树的merge操作中,每次merge都添加一个新节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int merge(int x,int y)
{
    if(!x||!y) return x|y;
    if(t[x].val>t[y].val)
    {
        swap(x,y);
	}
    int p=++cnt;
    t[p]=t[x];
    t[p].rs=merge(t[p].rs,y);
    if(t[t[p].rs].dist>t[t[p].ls].dist)
    {
        swap(t[p].rs,t[p].ls);
    }
    t[p].d=t[t[p].rs]+1;
    return p;
}

时间复杂度与空间复杂度均为qlogN