什么是左偏树 (堆):
左偏树是一种比较常用的可并二叉堆. 支持在最坏 \(O(log\
n)\) 的时间复杂度内进行堆的合并操作.
相关定义:
外结点: 左儿子或右儿子为空的结点.
距离: 一个结点到离它最近的外结点的距离。特殊地，
外结点本身距离为 0, 空结点距离为 - 1.
左偏树的性质及结论:
左偏树满足堆性质.
左偏树满足左偏性质 , 即对于每个结点，
其左子结点距离 \(d_{ls}\) 大于等于右子结点距离 \(d_{rs}\).
由 2, 结点 \(x\) 的距离 \(d_x = d_{rs} + 1\).
根结点距离为 \(d\) 的左偏树最少有 \(2^{n+1}-1\) 个结点，
此时该树为一个满二叉树.
同 4, \(n\) 个结点的左偏树距离最大为 \(log_2n\).
基本操作:
左偏树最基本操作便是合并操作.
定义函数 merge(x,y), 作用是将根为 \(x, y\) 的两个堆合并，返回合并后堆的根.
以小根堆为例，基本步骤如下:
- 若 \(x,y\) 其中有一个结点为空结点，
则返回另一个结点。否则下一步
- 若 \(v_x<v_y\), 则以 \(x\) 作为合并后的根结点，否则以 \(y\) 作为根结点。为避免讨论，当 \(v_x \geq v_y\) 时，直接交换 \(x,y\).
- 将 \(y\) 与 \(x\) 的左儿子进行合并，即 \(ls_x=merge(ls_x,y)\).
- 合并完成后维护左偏性质：当 \(d_{ls}<d_{rs}\) 时交换左右儿子.
示例代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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]);
}
}
}
return 0;
}
|