简介
左偏树是一种具有左偏性质的堆有序二叉树
下面给出左偏树最重要的定义
一个节点的距离为其到最近的叶子节点的距离，叶子节点的距离我们认为是 $0$，实现的时候为了方便我们令其为 $-1$
性质
- 任何一个节点的值必定小于左右儿子的值
- 任何一个节点的左儿子的距离大于等于右儿子的距离
- 一个节点的距离等于右儿子的距离加一
- 任何时候，一个节点数为 $n$ 的左偏树，距离最大的节点的距离为 $\log(n+1)-1$
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #define lc T[x].ch[0]
#define rc T[x].ch[1]
struct Left_Leaning_Tree {
int v, d, ch[2];
} T[maxn]; int f[maxn];
inline void maintain(int x) {
}
inline void pushdown(int x) {
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (T[x].v > T[y].v) swap(x, y);
pushdown(x); rc = merge(rc, y); f[rc] = x;
if (T[lc].d < T[rc].d) swap(lc, rc);
T[x].d = T[rc].d + 1; maintain(x);
return x;
}
|
可以维护的东西
两个左偏树合并
时间复杂度 $O(\log n)$
删除左偏树的根，即左偏树的最小值
时间复杂度 $O(\log n)$
例题
要求实现两个操作，支持合并两个数所在的小根堆，删除某个数所在的小根堆的最小的元素
Luogu P3377 【模板】左偏树（可并堆） 需要额外使用并查集