左偏树属于可并堆的一种，可并堆，也就是可以在较低的时间复杂度下完成对两个堆的合并。
定义及性质
对于一棵二叉树，定义外节点为左儿子或右耳子为空的节点，定义其的 (dist) 为 (1)，而不是外节点的 (dist) 为其到子树中最近的外节点距离 (+1)。空节点的 (dist) 为 (0)。 例如，对于这一棵二叉树，其的外节点和 (dist) 如下：
定义：有一棵二叉树，如果它不仅满足堆的性质，对其的每一个节点都有左儿子的 (dist) 大于等于右儿子的 (dist)，则称其为“左偏树”。为什么会“左偏”呢？不妨举几个例子：
其中，前两个为左偏树，可以发现，它们确实是向左偏的；而后两棵树不是左偏树，因为标红的节点其左儿子的 (dist) 小于右儿子，值得注意的是，第四幅图根节点没有左儿子，根据定义，空节点的 (dist) 为 (0)，比右儿子的 (1) 小，所以其为左偏树。
性质：
-
对于任意一个非外节点，(dist_u=dist_{rson}+1)。根据 (dist) 的定义，(dist_u) 要么为左儿子 (dist) 加一，要么为右儿子 (dist) 加一，由于要求是“最近”的外节点，加上左偏树的性质，(dist_u=dist_{rson}+1)。
-
一课左偏树的 (dist) 最大值在 (log n) 级别。假设根的 (dist) 为 (x)，则这棵二叉树至少前 (x-1) 层为“满的”，那么就至少有 (2^x-1) 个节点，注意到，这一点对任何一棵二叉树都适用。还有重要的是左偏树的深度没有任何保证，一条向左偏的链仍然是左偏树，只有其的 (dist) 最大值有保证。
合并操作
左偏树的核心是合并操作。下文以小根堆为例。
首先，为了满足堆性质，应取两个堆中根较小的那个根作为新的根，作为根的堆左儿子不动，把右儿子和另一个堆合并，一直递归下去，而为了满足左偏树的性质，如果左儿子的 (dist) 比右儿子小了，应交换其左右儿子（实际上，还有一种不用交换的方法，就是把 (dist) 小的那个儿子之间当做右儿子）。
以下是一个例子（节点中的数为值，红色的数为 (dist)）：
时间复杂度：由于每递归一层，其中一个堆的根的 (dist) 就会减 (1)，根据 (dist) 的最大值在 (log) 级别的性质，合并的时间复杂度为 (O(log x+log y))（其中 (x,y) 为两个堆的大小）。
int merge(int x, int y) {
if (!x || !y) return x | y;
//如果其中有一个堆为空的话就返回另一个堆
if (t[x].v > t[y].v) swap(x, y);//选根较小的堆
t[x].rs = merge(t[x].rs, y);//合并右儿子
if (t[t[x].rs].dist > t[t[x].ls].dist) swap(t[x].rs, t[x].ls);
//使其保持左偏堆的性质
t[x].dist = t[t[x].rs].dist + 1;//更新 dist
return x;
}
其它操作
插入元素：直接把这一个节点当成一个堆，合并即可。
删除根：合并根的左右儿子。
删除任意节点：将左右儿子合并并从下往上更新 (dist) 并通过交换左右儿子维护左偏树的性质，(dist) 不更新时结束递归，时间复杂度 (O(log n))。
整个堆加或乘一个数：在根上打上标记，合并时下传即可。
具体实现
一开始有 (n) 个小根堆，你需要支持以下两个操作：
- 合并 (x) 和 (y) 所在的堆，若 (x) 或 (y) 已经在同一个堆中或已被删去则忽略；
- 查询第 (x) 个堆的堆顶并弹出，若 (x) 被删去则输出
-1。
(1le nle 10^5)。
分析：其实两个操作在之前都讲过了，不过注意对于查询堆顶或判断是否在同一个堆中，警惕以下错误的写法：
int Get(int x) {
while(S[x].F) x = S[x].F;
return x;
}
这相当于暴力跳父亲。之前说过，左偏树的深度是没有保障的，这样的方法有可能被卡到 (O(n))。正确的做法是使用并查集+路径压缩维护，复杂度近似于 (O(log n))。
然后还有一个常会犯的错误是当弹出堆顶时，（并查集维护）堆顶的祖先应更改为合并后的根节点。虽然这个点以后不会用到了，但是之前把它当做祖先的点仍会访问到它（因为使用了路径压缩），于是就会导致找到错误的根节点。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
namespace Leftist_tree {
int fa[N];
bool vis[N];
struct node {
int v;
int ls, rs;
int dist;
}t[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (t[x].v > t[y].v) swap(x, y);
t[x].rs = merge(t[x].rs, y);
if (t[t[x].rs].dist > t[t[x].ls].dist) swap(t[x].rs, t[x].ls);
t[x].dist = t[t[x].rs].dist + 1;
return x;
}
}
using namespace Leftist_tree;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), std::cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> t[i].v, fa[i] = i;
while (m--) {
int op, x, y;
cin >> op >> x;
if (op == 1) {
cin >> y;
if (vis[x] || vis[y] || find(x) == find(y)) continue;
fa[find(x)] = fa[find(y)] = merge(find(x), find(y));
}
else {
if (vis[x]) cout << "-1n";
else {
x = find(x), vis[x] = true, cout << t[x].v << "n";
fa[x] = fa[t[x].ls] = fa[t[x].rs] = merge(t[x].ls, t[x].rs);
}
}
}
return 0;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
