左偏树 顾名思义 向左偏的树 （原题入口）
它有啥子用呢？？？ 当然是进行堆的合并啦2333
普通堆的合并其实是有点慢的(用优先队列的话 只能 一个pop 一个push 来操作 复杂度就是O(n log n))
而左偏树就特别快 (一个堆可以一次性合并 复杂度只需O(log n) )
左偏树共有 3条性质: (来自于百度百科)
[性质1] 节点的键值小于或等于它的左右子节点的键值。 //这个性质普通堆都具有 不用深究 学过二叉堆的都知道
[性质2] 节点的左子节点的距离不小于右子节点的距离。
这条就是它为啥叫左偏树的原因，接下来讲讲啥是距离。 距离就是 一个节点 到它后代最近的外节点所经过的边数
外节点又是啥呢 就是左右子树有一个为空(NULL) 的节点。由定义易得,外节点的距离就是0。
由这两条性质，我们可以得出左偏树的定义：左偏树是具有左偏性质的堆有序二叉树。
[性质3] 节点的距离等于它的右子节点的距离加1。
这个是为啥得出呢 由性质2可以推出来 对于一个外节点 它的左子节点距离不小于右子节点距离的话 那它的右子树必为空
我们又从下向上推 它右子节点距离更小的话 那么 它显然经过右子节点能到它的最近外节点
[引理1] 若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。
[定理1] 若一棵左偏树的距离为k，则这棵左偏树至少有2^(k+1)-1个节点。
[性质4] 一棵N个节点的左偏树距离最多为log(N+1)-1。
这几条性质都可以由[性质2]推出 然而我并不知道有啥用qwq 有兴趣的可以去看看大牛的博客
下一段也是摘抄自百度百科 解释为啥它合并这么快:
我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。
左偏树并不是为了快速访问所有的节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。
从图中我们可以看到它并不平衡，由于性质2的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，
左偏树并不意味着左子树的节点数或是深度一定大于右子树。
它最重要的代码就是合并 我按我蒟蒻的理解随便讲讲算了(好敷衍。。):
1.首先如果合并一个实树(自定义。。就是有节点的树) 和一个空树 直接返回那个实树
2.其次我们是要求小根堆 就要将 key 小的节点放在根节点 我们默认为A 所以如果 key(A) > key(B) 那么我们就交换
3.之后我们就将 B 接到 A 的右子树上面 (至于为啥不能是左子树 我也不知道QAQ 不是左偏树么。。)
4.然后看看 A左右子树的距离 如果左子树距离要小于右子树 那么直接交换左右子树 为了满足[性质2]
5.接下来我们更新 A 的距离 如果为外节点(右子树为空) 那么直接为0 否则 为 右子树距离 + 1
这是是用递归实现的合并 每次合并后 应该返回合并后的根节点下标 (也就是我写的小merge,大Merge是合并两个堆的根的)
看看代码。。。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <iostream>
#define For(i, l, r) for(int i = (l); i <= (int)(r); ++i)
#define Fordown(i, r, l) for(int i = (r); i >= (int)(l); --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std; inline int read(){
int x = , fh = ; char ch;
for(; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -;
for(; isdigit(ch); ch = getchar()) x = (x<<) + (x<<) + (ch^'');
return x * fh;
} struct node {
int lc, rc, val; //分别是left_child左儿子, right_child右儿子, value 键值
};
const int max_node = ; //最大子节点个数
node lt[max_node]; //leftist_tree 左偏树
int dist[max_node], fa[max_node]; //左偏树距离dist:到最右叶子节点边的条数
//并查集父亲数组fa void make_tree (int x) {
lt[x].lc = lt[x].rc = dist[x] = ; //清空它的左右儿子和距离（新建一个树）
} int merge (int a, int b) { //合并两个可以合并的树 返回合并后的父节点
if (a == ) return b; //a为空 返回b
if (b == ) return a; //b为空 返回a
if (lt[a].val > lt[b].val) swap(a, b); //将根节点设为a（值较小的那个）
lt[a].rc = merge(lt[a].rc, b); fa[lt[a].rc] = a; //将b合并到a的右子树上 并将右子树父亲设为a
if (dist[lt[a].rc] > dist[lt[a].lc]) swap(lt[a].lc, lt[a].rc); //右子节点距离大于左子节点 不符合左偏树性质则交换左右子树
if (lt[a].rc == ) dist[a] = ; //右子树为空 距离为0 即直接到自己
else dist[a] = dist[lt[a].rc] + ; //否则按照性质 距离为右子节点的距离+1
return a; //返回a节点
} int find (int x) {
return fa[x] = fa[x] == x ? x : find(fa[x]); //并查集操作
} void Merge (int a, int b) { //合并两个数
int root_a = find(a), root_b = find(b);
if (root_a == root_b) return ; //在同一个堆里就不合并
if (lt[a].val == || lt[b].val == ) return ; //这个数已被删掉也不合并
// cout << "merge: " << root_a << ' ' << root_b << endl;
int tmp = merge(root_a, root_b);
fa[root_a] = fa[root_b] = tmp; //将两个节点父亲设为合并后的父亲
} void delete_min (int a) {
int root_a = find(a); //找到堆顶
if (lt[a].val == ) {printf ("-1\n"); return;} //已被删除 输出-1
// cout << "find: " << root_a << endl;
printf ("%d\n", lt[root_a].val); //输出堆顶的值
int tmp = merge (lt[root_a].lc, lt[root_a].rc); //合并这个堆顶的左右子树
fa[lt[root_a].lc] = fa[lt[root_a].rc] = fa[root_a] = tmp; //将左右子树和原来根节点的父亲设为它们合并后的父亲
lt[root_a].lc = lt[root_a].rc = lt[root_a].val = ; //删除堆顶
} int main(){
int n = read(), m = read();
For (i, , n) {
lt[i].val = read();
make_tree(i);
fa[i] = i;
}
while (m--) {
int opt = read();
if (opt == ) {
int a = read(), b = read();
Merge(a, b);
}
else {
int a = read();
delete_min(a);
}
}
}
Update 2018-4-8
当年的代码写的好丑啊qwq 再挂一个新的码风的代码...
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std; void File() {
#ifdef zjp_shadow
freopen ("P3377.in", "r", stdin);
freopen ("P3377.out", "w", stdout);
#endif
} const int N = ; int fa[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } struct Lefist_Tree {
int val[N], ls[N], rs[N], dis[N]; int Merge(int a, int b) {
if (!a || !b) return a | b;
if (val[a] > val[b]) swap(a, b);
rs[a] = Merge(rs[a], b); fa[rs[a]] = a;
if (dis[rs[a]] > dis[ls[a]]) swap(ls[a], rs[a]);
if (!ls[a]) dis[a] = ;
else dis[a] = dis[ls[a]] + ;
return a;
} void Opt_Merge(int a, int b) {
int rta = find(a), rtb = find(b);
if (rta == rtb) return ;
if (!val[a] || !val[b]) return ;
fa[rta] = fa[rtb] = Merge(rta, rtb);
} int Opt_Delete(int a) {
if (!val[a]) return -;
int rta = find(a), res = val[rta];
int tmp = Merge(ls[rta], rs[rta]);
fa[ls[rta]] = fa[rs[rta]] = fa[rta] = tmp;
ls[rta] = rs[rta] = val[rta] = ;
return res;
} void Make_Tree(int x) {
ls[x] = rs[x] = val[x] = ;
}
} T; int n, m; int main () {
File();
scanf ("%d%d", &n, &m);
For (i, , n) T.Make_Tree(i), scanf ("%d", &T.val[i]), fa[i] = i;
For (i, , m) {
int opt;
scanf ("%d", &opt);
if (opt == ) { int a, b; scanf ("%d%d", &a, &b); T.Opt_Merge(a, b); }
else { int a; scanf ("%d", &a); printf ("%d\n", T.Opt_Delete(a)); }
}
return ;
}