左偏树小结

左偏树小结

出现了!看起来很niubi的数据结构怪!大师球!

(本文的思路大都来自https://blog.csdn.net/wang3312362136/article/details/80615874和http://www.cnblogs.com/yyf0309/p/LeftistTree.html 中,加入了一些个人理解。侵删。)

食用指南

1.本文中的‘距离’指普通意义下的距离,而距离指左偏树中节点的距离

2.本文中默认所有左偏树和堆都是大根堆

3.本文中的log都以2为底数

一个问题

假如现在给你两个大小为s1,s2的堆,要求你将这两个堆合并,并保证合并后仍符合堆的性质,时间复杂度$O(log(s1\times s2))$。

什么?log?这不可能做的吧……

但是!万事皆有可能!匹配堆斐波那契堆左偏树就是能解决这种问题的一种非常神奇的东西!

几个定义

学名leftist treeleftist heap。What?heap?没错,其实左偏树就是一个堆。

首先既然是堆,那么他就满足堆的性质:

  1. 这是一棵二叉树,而且父亲的值大于左右儿子的值

然后有几个定义:

外节点:一个节点被定义为外节点当且仅当这个节点的左子树或右子树是空节点

点的距离($dis$):空节点默认距离为-1,非空节点的距离为它子树中离他最近的外节点到这个节点的‘距离’。外节点本身距离为0。

左偏树

它为什么叫左偏树

这与它的性质有关。

  1. 左偏树中任意一个节点的左儿子的距离一定大于等于右儿子的距离(左偏性质)
  2. 左偏树中的任意节点的左子树和右子树(如果有的话)都是左偏树

比较有意思的性质

推论1. 左偏树中任意一个节点的距离为其右儿子的距离+1,也就是$dis_x = dis_{rx} + 1$。

这是显然的。根据定义,$dis_x = min(dis_{lx},dis_{rx})+1$,而又由性质2得$dis_{lx}$必然大于$dis_{rx}$,得证。

推论2. $n$个点的左偏树,距离最大为$\lfloor log(n+1)\rfloor−1$。

考虑左偏树根节点的距离d为一定值,那么节点数最少的情况就是一个完全二叉树,节点数为$2^{d+1}−1$。那么$n$个节点的左偏树距离也就$≤\lfloor log(n+1)\rfloor−1$。 同时由此我们还可知:一棵有n个节点的左偏树的最右链,至多有$\lfloor log(n+1)\rfloor$个节点。

推论2保证了左偏树时间复杂度的正确性。

推论3:左偏树的最右链恰好有1个外结点。

接下来我们进入到代码实现。

操作:合并(Merge)

现在有两棵左偏树,a,b分别是它们的根节点,且$val_a \leq val_b$。那么合并后为了保证堆性,显然要让a成为根节点。那么现在问题变成了:递归合并$b$,和$la$或$ra$。这里随便选一个合并就行,因为显然不论与哪个合并,我们都只保证了了它满足作为堆的性质,却不一定能让其满足左偏性质,因为点之间的距离是变化的。因此我们假设这里就递归合并$b$和$ra$,并将新树的根节点作为a的右儿子。这个操作是递归进行的,递归到底部开始回溯时,我们再来考虑左偏性质,如果不满足(即$dis_{la}<dis_{ra}$),那么我们就交换a的左右儿子。

1
2
3
4
5
6
7
8
9
10
11
int Merge(int x, int y) {
if (x == 0) return y;
if (y == 0) return x;
if (v[x] > v[y] || (v[x] == v[y] && x > y)) swap(x, y);
t[x][1] = Merge(t[x][1], y);
fa[t[x][1]] = x;
if (d[t[x][0]] < d[t[x][1]])
swap(t[x][0], t[x][1]);
d[x] = d[t[x][1]] + 1; //推论1
return x;
}

注意到这里要使用到并查集,而并查集是不能使用路径压缩的,因为我们需要知道他的直接父亲节点而不是根节点。

时间复杂度?

本文开头。

操作:Push,Pop

push:向左偏树中插入一个节点。

其实就是一个只有一个节点的左偏树与一棵有很多节点的左偏树合并。

pop:删除节点。

将根的左右儿子合并,然后将新合并的树的父亲设为NULL。

两个操作的时间复杂度都是$O(log~n)$

操作:Build

给数组$a_i$建一棵左偏树

暴力push,时间复杂度是$O(\sum\limits_{i=1}^nlog~i)$,等价于$O(log(\prod\limits_{i=1}^{n}i))$,其实就是$O(log ~n!)$。这个东西比$O(n~log~n)$稍微小一点。

如果像普通堆一样建左偏树,建一个队列存a数组,每次取出队列头两个节点,Merge后丢到队列尾去。时间复杂度$O(n)$

代码实现

luoguP3377 【模板】左偏树(可并堆)

暴力插入,暴力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
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
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100010;
int n, m, v[MAXN];
int fa[MAXN], t[MAXN][2], d[MAXN];

template <typename _Tp>
inline void read(_Tp &x) {
char ch = getchar( ); bool f = 0; x = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar( ); }
x = f ? -x : x;
}

int Merge(int x, int y) {
if (x == 0) return y;
if (y == 0) return x;
if (v[x] > v[y] || (v[x] == v[y] && x > y)) swap(x, y);
t[x][1] = Merge(t[x][1], y);
fa[t[x][1]] = x;
if (d[t[x][0]] < d[t[x][1]])
swap(t[x][0], t[x][1]);
d[x] = d[t[x][1]] + 1;
return x;
}

int find(int x) { while(fa[x]) x = fa[x]; return x; }

void Pop(int x) {
v[x] = -1;
fa[t[x][0]] = fa[t[x][1]] = 0;
Merge(t[x][0], t[x][1]);
}

int main( ) {
read(n), read(m);
d[0] = -1;
for (int i = 1; i <= n; ++ i) read(v[i]);
int opt, x, y, r1, r2;
for (int i = 1; i <= m; ++ i) {
read(opt);
if (opt == 1) {
read(x), read(y);
if (v[x] == -1 || v[y] == -1) continue;
if (x == y) continue;
r1 = find(x), r2 = find(y);
Merge(r1, r2);
}
else {
read(x);
if (v[x] == -1) printf("-1\n");
else {
y = find(x);
printf("%d\n",v[y]);
Pop(y);
}
}
}
return 0;
}
{% if theme.fireworks %} {% endif %} {{ live2d() }}