左偏树：可并堆的高效实现
左偏树是一种特殊的可并堆数据结构，它不仅具备堆的基本特性，还能高效地执行合并操作。本文将详细介绍左偏树的原理、性质及实现方法。
基础知识回顾
优先队列 在算法竞赛中，我们经常使用优先队列进行优化。例如，使用C++的STL库可以这样实现：
priority_queue<int, vector<pair<int,int> >, greater<pair<int,int> > > q;
这会创建一个按照距离值（first元素）从小到大排序的队列，其中距离值就是键值。
二叉堆 二叉堆是一种特殊的完全二叉树，每个节点存储一个元素（或权值）。堆的性质要求：对于任意节点，其权值不小于其子节点的权值（大根堆），反之则为小根堆。
左偏树的定义
左偏树是一种可并堆的实现形式，它是一棵二叉树，每个节点除了左右子树指针外，还包含两个重要属性：键值（key）和距离（dist）。键值用于节点间的比较。
距离的定义与性质：
- 当一个节点的左子树或右子树为空时，该节点称为外节点（external node）
- 节点i的距离（dist(i)）是从i到其后代中最近外节点所经过的边数
- 如果节点本身是外节点，则其距离为0
- 空节点的距离定义为-1
- 一棵左偏树的距离通常指其根节点的距离
左偏树示意图
外节点示意图
核心性质
val表示key，即键值
左偏性质： 每个节点的左儿子的dist都大于等于右儿子的dist。因此，左偏树每个节点的dist都等于其右儿子的dist加一。需要注意的是，dist并不是深度，一条向左的链也是合法的左偏树。
性质1： 满足堆的性质，对于任意节点p，val[p] ≥（或≤）val[l], val[r]。
性质2： dist[x] = dist[r] + 1，即任意节点的距离等于其右子树的距离加1。
重要定理
定理： 对于包含n个节点的左偏树，其最大距离不超过log(n+1)−1，即max{dist} ≤ log(n+1)-1。
证明：设max{dist}=k，则节点数最少的左偏树是一棵完全二叉树，此时节点数为2^(k+1)-1，因此n ≥ 2^(k+1)-1，移项得：k ≤ log(n+1)-1。
引理： 如果一棵左偏树的距离为k，则这颗左偏树最少包含2^(k+1)−1个节点。
证明：由于左偏树的左子树距离一定大于等于右子树的距离，且左偏树的距离等于右子树距离加一，那么当节点数最少时，任意节点的左子树大小等于右子树大小，满足这样性质的二叉树就是完全二叉树。
基本操作实现
合并（merge） 合并两个堆时，首先选取键值较小（或较大）的根作为新堆的根节点，然后将该根的左儿子作为新堆的左儿子，递归地合并其右儿子与另一个堆作为新堆的右儿子。为满足左偏性质，合并后若左儿子的dist小于右儿子的dist，则交换两个儿子。
代码实现
int unite(int x, int y) {
if (!x || !y) return x + y; // 若有一个堆为空，返回另一个堆
if (tree[x].key > tree[y].key || (tree[x].key == tree[y].key && x > y)) swap(x, y);
// 满足堆性质，取较小值作为根
tree[x].right = unite(tree[x].right, y);
tree[tree[x].right].parent = x; // 更新父节点
if (tree[tree[x].left].dist < tree[tree[x].right].dist)
swap(tree[x].left, tree[x].right); // 左偏性质
tree[x].dist = tree[tree[x].right].dist + 1; // 更新距离
return x;
}
主函数中：
int X = find(x), Y = find(y);
if (X != Y)
tree[X].parent = tree[Y].parent = unite(X, Y);
插入节点 将待插入节点视为一个单节点堆，使用上述合并操作将其与目标堆合并即可。
代码实现
tree[x].parent = tree[y].parent = unite(x, y); // x是待插入节点，y是目标堆
删除根节点 将根节点的键值设为特殊值（表示已删除），然后合并其左右子树即可。
代码实现
void remove_root(int x) {
tree[x].key = -1; // 标记为已删除
tree[tree[x].left].parent = tree[x].left; // 更新子节点的父节点
tree[tree[x].right].parent = tree[x].right;
tree[x].parent = unite(tree[x].left, tree[x].right); // 合并子树
}
【模板】左偏树（可并堆）
分析
本题是左偏树的基本应用，主要使用合并和删除操作。实现小根堆功能。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, m, op, x, y;
struct Node {
int left, right, parent, dist, value;
} tree[MAXN];
int find(int x) { // 并查集查找操作
if (tree[x].parent == x) return x;
tree[x].parent = find(tree[x].parent);
return tree[x].parent;
}
int unite(int x, int y) {
if (!x || !y) return x + y;
if (tree[x].value > tree[y].value || (tree[x].value == tree[y].value && x > y)) swap(x, y);
tree[x].right = unite(tree[x].right, y);
tree[tree[x].right].parent = x;
if (tree[tree[x].left].dist < tree[tree[x].right].dist)
swap(tree[x].left, tree[x].right);
tree[x].dist = tree[tree[x].right].dist + 1;
return x;
}
void remove_root(int x) {
tree[x].value = -1;
tree[tree[x].left].parent = tree[x].left;
tree[tree[x].right].parent = tree[x].right;
tree[x].parent = unite(tree[x].left, tree[x].right);
}
int main() {
cin >> n >> m;
tree[0].dist = -1; // 初始化空节点的距离
for (int i = 1; i <= n; i++) {
cin >> tree[i].value;
tree[i].parent = i; // 初始化每个节点为独立堆
}
for (int i = 1; i <= m; i++) {
cin >> op >> x;
if (op == 1) {
cin >> y;
if (tree[x].value == -1 || tree[y].value == -1) continue;
int X = find(x), Y = find(y);
if (X != Y)
tree[X].parent = tree[Y].parent = unite(X, Y);
} else {
if (tree[x].value == -1) {
puts("-1");
} else {
int X = find(x);
printf("%d\n", tree[X].value);
remove_root(X);
}
}
}
return 0;
}
罗马游戏
分析
简化题意：当命令为'M'时合并两个堆；当命令为'K'时删除分数最低元素，因此需要实现小根堆。
注意：若元素已被删除，应输出0，而不是-1。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int n, m, x, y;
struct Node {
int left, right, parent, value, dist;
} tree[MAXN];
char op;
int unite(int x, int y) {
if (!x || !y) return x + y;
if (tree[x].value > tree[y].value || (tree[x].value == tree[y].value && x > y)) swap(x, y);
tree[x].right = unite(tree[x].right, y);
tree[tree[x].right].parent = x;
if (tree[tree[x].left].dist < tree[tree[x].right].dist)
swap(tree[x].left, tree[x].right);
tree[x].dist = tree[tree[x].right].dist + 1;
return x;
}
int find(int x) {
if (tree[x].parent == x) return x;
tree[x].parent = find(tree[x].parent);
return tree[x].parent;
}
void remove_root(int x) {
tree[x].value = -1;
tree[tree[x].left].parent = tree[x].left;
tree[tree[x].right].parent = tree[x].right;
tree[x].parent = unite(tree[x].left, tree[x].right);
}
int main() {
scanf("%d", &n);
tree[0].dist = -1;
for (int i = 1; i <= n; i++)
scanf("%d", &tree[i].value), tree[i].parent = i;
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
cin >> op; scanf("%d", &x);
if (op == 'M') {
scanf("%d", &y);
if (tree[x].value == -1 || tree[y].value == -1) continue;
int X = find(x), Y = find(y);
if (X != Y)
tree[X].parent = tree[Y].parent = unite(X, Y);
} else {
if (tree[x].value == -1) {
puts("0");
} else {
int X = find(x);
printf("%d\n", tree[X].value);
remove_root(X);
}
}
}
return 0;
}
Monkey King
分析
本题是左偏树应用的经典例题。简化题意：使x和y的值减半后重新合并，并输出合并后堆的根。若两个猴子在同一个堆中，输出-1。与前面题目不同的是，本题需要实现大根堆，因为每次都是值最大的元素进行战斗。
因此，在合并时只需将比较条件改为：
if (tree[x].value < tree[y].value) swap(x, y);
注意：本题是多测数据，需要记得清空数组。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, m, x, y;
struct Node {
int left, right, parent, value, dist;
} tree[MAXN];
int find(int x) {
if (tree[x].parent == x) return x;
tree[x].parent = find(tree[x].parent);
return tree[x].parent;
}
int unite(int x, int y) {
if (!x || !y) return x + y;
if (tree[x].value < tree[y].value) swap(x, y);
tree[x].right = unite(tree[x].right, y);
tree[tree[x].right].parent = x;
if (tree[tree[x].left].dist < tree[tree[x].right].dist)
swap(tree[x].left, tree[x].right);
tree[x].dist = tree[tree[x].right].dist + 1;
return x;
}
int remove_root(int x) {
tree[x].value >>= 1;
int new_root = unite(tree[x].left, tree[x].right);
tree[x].left = tree[x].right = 0;
tree[x].dist = -1;
return tree[x].parent = tree[new_root].parent = unite(new_root, x);
}
int main() {
while (cin >> n) {
memset(tree, 0, sizeof(tree));
tree[0].dist = -1;
for (int i = 1; i <= n; i++) {
scanf("%d", &tree[i].value);
tree[i].parent = i;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
int X = find(x), Y = find(y);
if (X == Y) {
puts("-1");
} else {
int l = remove_root(X), r = remove_root(Y);
tree[l].parent = tree[r].parent = unite(l, r);
printf("%d\n", tree[tree[l].parent].value);
}
}
}
return 0;
}
左偏树的应用非常广泛，除了上述提到的操作外，还可以实现更多高级功能，如堆的分裂、查找第k大元素等。掌握左偏树的原理和实现，对于解决各类数据结构问题都具有重要意义。
