- 作者：zifeiy
- 标签：左偏树
这篇随笔需要你在之前掌握 堆 和 二叉树 的相关知识点。
堆支持在 \(O(\log n)\) 的时间内进行插入元素、查询最值和删除最值的操作。在这里，如果最值是最小值，那么这个堆对应地称为小根堆；如果最值是最大值那么这个堆对应地称为大根堆。
当然咯，在我们的STL容器中提供了优先队列（priority_queue），可以直接用它来模拟堆。
但是，priority_queue 不涉及合并两个堆的操作（pb_ds有这样的功能），这就是说，如果现在有两个堆 A 和 B，我要将堆 B 中的元素全部合并到堆 A 中，则我需要遍历 A 中的每个元素，然后将其插入堆 A 中，时间复杂度为 \(O(n \times \log n)\) 。
而我们这里要讲的 左偏树 是什么呢？
- 首先，左偏树也具有堆的性质；
- 其次，能够实现在 \(O(\log n)\) 的时间复杂度范围内合并两个左偏树。
左偏树的每一个节点上都存放4个信息：左、右儿子的地址，权值，距离。
权值 就是每一个节点存放的数值信息；
距离 表示这个节点到它子树里面最近的叶子节点的距离。（叶子节点的距离为0）
左偏树的性质
- 性质一：节点的权值小于等于它左右儿子的权值。
- 性质二：节点的左儿子的距离 \(\ge\) 右儿子的距离。
- 性质三：节点的距离=右儿子的距离+1。
- 性质四：一个n个节点的左偏树距离最大为 \(\log (n+1)-1\)
对于性质二：
在写平衡树的时候，我们是确保它的深度尽量的小，这样访问每个节点都很快。但是左偏树不需要这样，它的目的是快速提取最小节点和快速合并。所以它并不平衡，而且向左偏。但是距离和深度不一样，左偏树并不意味着左子树的节点数或是深度一定大于右子树。
对于性质四，我们可以采取以下方式来证明：
若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。
节点最少的话，就是左右儿子距离一样，这就是完全二叉树了。
若一棵左偏树的距离为k，则这棵左偏树至少有 \(2^{k+1}-1\) 个节点。
距离为k的完全二叉树高度也是k，节点数就是 \(2^{k+1}-1\) 。
这样就可以证明性质四了。因为 \(n \ge 2^{k+1}-1\) ，所以 \(k \le \log (n+1)-1\) 。
左偏树的操作
1、合并
我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树和B了。
合并了A的右子树和B之后，A的右子树的距离可能会变大，当A的右子树 的距离大于A的左子树的距离时，性质二会被破坏。在这种情况下，我们只须要交换A的右子树和左子树。
而且因为A的右子树的距离可能会变，所以要更新A的距离=右儿子距离+1。这样就合并完了。
代码：
int func_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);
son[x][1] = func_merge(son[x][1], y);
f[ son[x][1] ] = x;
if (dis[ son[x][0] ] < dis[ son[x][1] ])
swap(son[x][0], son[x][1]);
dis[x] = dis[ son[x][1] ] + 1;
return x;
}
在合并x和y的过程中，如果其中有一个节点是空节点，则直接返回非空节点的编号；
因为我们这里模拟的是一个小根堆，所以我们要确保权值小的作为根节点（权值相同的情况下编号小的作为根节点，虽然这一步不是必需的，但是方便梳理）。
假设现在选出了根节点x，那么我们再递归地去合并x的右子树和y，并将合并的结果作为x的左子树，将x原先的左子树作为x的右子树。
同时更新x节点的距离。
我们可以看出每次我们都把它的右子树放下去合并。因为一棵树的距离取决于它右子树的距离(性质三)，所以拆开的过程不会超过它的距离。根据性质四，不会超过 \(\log (n_x+1) + \log (n_y+2) - 2\) ，时间复杂度就是 \(O(\log n_x + \log n_y)\) 。
2、插入
插入一个节点，就是把一个点和一棵树合并起来。
因为其中一棵树只有一个节点，所以插入的效率是 \(O(\log n)\) 。
3、删除最小/最大点
因为根是最小/大点，所以可以直接把根的两个儿子合并起来。
因为只合并了一次，所以效率也是 \(O(\log n)\) 。
然后我们再来看一下对应题目：洛谷P3377 【模板】左偏树（可并堆）
实现代码如下（88分）：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int son[maxn][2], val[maxn], dis[maxn], f[maxn], n, m, op, x, y;
int func_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);
son[x][1] = func_merge(son[x][1], y);
f[ son[x][1] ] = x;
if (dis[ son[x][0] ] < dis[ son[x][1] ])
swap(son[x][0], son[x][1]);
dis[x] = dis[ son[x][1] ] + 1;
return x;
}
int get_root(int x) {
return !f[x] ? x : get_root(f[x]);
}
void func_pop(int x) {
val[x] = -1;
f[ son[x][0] ] = f[ son[x][1] ] = 0;
func_merge(son[x][0], son[x][1]);
}
int main() {
scanf("%d%d", &n, &m);
dis[0] = -1;
for (int i = 1; i <= n; i ++) scanf("%d", val+i);
while (m --) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &x, &y);
if (val[x] == -1 || val[y] == -1 || x == y) continue;
int fx = get_root(x), fy = get_root(y);
func_merge(fx, fy);
}
else {
scanf("%d", &x);
if (val[x] == -1) puts("-1");
else {
y = get_root(x);
printf("%d\n", val[y]);
func_pop(y);
}
}
}
return 0;
}
但是上面的代码最后一组数据会超时，因为它没有进行路径压缩。
我们可以在原来代码的基础上采用 并查集 来进行路径压缩。
我们可以发现，原来的代码中，如果一个节点x是根节点，那么 \(f[x]==0\) 。
而我实现并查集的代码是：如果一个节点x是根节点，那么 \(f[x]==x\) 。
所以我在 get_root(int x) 函数中使用并查集进行了路径压缩。
但是，这里有一个问题，就是这里面临着删除元素，那么如果删除了一个元素，我们又能对并查集进行如何的修改呢？
首先，删除元素x的操作见 func_pop(int x) 函数。
首先需要将 vis[x] 置为 -1 。
然后需要将x的左右儿子节点都置为它们本身（左右儿子都回归到了根节点）。
最后，最最需要注意的地方是，虽然x已经删除了，但是x可能对应其余一些节点的父节点，在合并了x的左右儿子之后还需要将x的父节点设为新的根节点，这样就能够将其它当前的父节点还保存是x的节点正确引导向新的根节点，即补充下面这行代码：
f[x] = func_merge(son[x][0], son[x][1]);
AC代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int son[maxn][2], val[maxn], dis[maxn], f[maxn], n, m, op, x, y;
int func_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);
son[x][1] = func_merge(son[x][1], y);
f[ son[x][1] ] = x;
if (dis[ son[x][0] ] < dis[ son[x][1] ])
swap(son[x][0], son[x][1]);
dis[x] = dis[ son[x][1] ] + 1;
return x;
}
int get_root(int x) {
return x == f[x] ? x : (f[x] = get_root(f[x]));
}
void func_pop(int x) {
val[x] = -1;
f[ son[x][0] ] = son[x][0];
f[ son[x][1] ] = son[x][1];
f[x] = func_merge(son[x][0], son[x][1]);
}
void init() {
for (int i = 1; i <= n; i ++) f[i] = i;
}
int main() {
scanf("%d%d", &n, &m);
dis[0] = -1;
for (int i = 1; i <= n; i ++) scanf("%d", val+i);
init();
while (m --) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &x, &y);
if (val[x] == -1 || val[y] == -1 || x == y) continue;
int fx = get_root(x), fy = get_root(y);
func_merge(fx, fy);
}
else {
scanf("%d", &x);
if (val[x] == -1) puts("-1");
else {
y = get_root(x);
printf("%d\n", val[y]);
func_pop(y);
}
}
}
return 0;
}