左偏树($Leftist\ Tree$)，是一种 __可以合并的堆状结构__，支持以下操作
- $Pop\ x$，删除节点$x$
- $Merge\ x\ y$，合并两棵左偏树
对于一个左偏树的节点，需要维护以下值
- $dist$，记录这个节点到它子树里面最近的叶子节点的距离
- $value$，每个节点包含的值
性质
- 一个节点的$value$大于(或小于)左右孩子的$value$(堆性质)
- 一个节点的左孩子的$dist$不小于右孩子的$dist$(左偏性质)
- 一个节点的距离始终等于右孩子+1
实现
$Merge$操作
首先我们设两个节点$x,y$，$x$的根节点的权值小于等于$y$的根节点（否则$swap(x,y)$），把$x$的根节点作为新树$Z$的根节点，剩下的事就是合并$x$的右子树和$y$了
合并了$x$的右子树和$y$后，$x$当$x$的右子树的距离大于$x$的左子树的距离时，为了维护左偏性质，我们要交换$x$的右子树和左子树。顺便维护性质三，所以直接$dist_x=dist_{rson(x)}+1$
$Pop$操作
略$…$
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
| struct LeftistTree {
int n, m;
struct LeftistTreeNode {
int dis, val, rt;
int ls, rs;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define dis(x) tree[x].dis
#define val(x) tree[x].val
#define rt(x) tree[x].rt
}tree[maxn];
int merge(int x, int y) {
if (!x || !y) return x + y;
if (val(x) > val(y) || (val(x) == val(y) && x > y)) {
swap(x, y);
}
rs(x) = merge(rs(x), y);
if (dis(ls(x)) < dis(rs(x))) swap(ls(x), rs(x));
rt(ls(x)) = rt(rs(x)) = rt(x) = x;
dis(x) = dis(rs(x)) + 1;
return x;
}
int get(int x) {
return rt(x) == x ? x : rt(x) = get(rt(x));
}
void pop(int x) {
val(x) = -1;
rt(ls(x)) = ls(x); rt(rs(x)) = rs(x);
rt(x) = merge(ls(x), rs(x));
}
void init() {
dis(0) = -1;
for (int i = 1; i <= n; ++i) {
rt(i) = i;
val(i) = read();
}
}
void SolveMerge(int x, int y) {
if (val(x) == -1 || val(y) == -1) return;
int fx = get(x), fy = get(y);
if (fx != fy) {
rt(fx) = rt(fy) = merge(fx, fy);
}
}
void SolvePop(int x) {
if (val(x) == -1) puts("-1");
else printf("%d\n", val(get(x))), pop(get(x));
}
};
|
$Luogu$模板题目
Luogu P3377 左偏树(可并堆)