一颗向左偏的树？一只可合并的堆？
前言
前几天，作者被同机房的$Logey$吊打了……然后$Logey$扔给了我一份目录
于是乎，作者便开始学习左偏树……
何为左偏树？
在学习左偏树之前，我们先来看看百度百科的解释
左偏树，也可称为左倾堆，可并堆，是计算机科学中的一种树，是一种优先队列实现方式，在信息学中十分常见，在统计问题、最值问题、贪心问题等类型的题目中，左偏树都有着广泛的应用。
——《百度百科》
嗯……
应该没人看懂吧（滑稽
毕竟您要看懂了，我就该退役了
还是来看看更加通俗一点的解释吧
左偏树是一种具有左偏性质的堆状二叉树，因此，左偏树是基于堆的（如果您不知道堆是什么请戳这里
可以看一下左偏树与普通二叉堆的对比：
|
插入 |
得到堆顶元素 |
弹出 |
合并 |
| 堆 |
$O(log n)$ |
$O(1)$ |
$O(log n)$ |
$O((n1+n2)log(n1+n2))$ |
| 左偏树 |
$O(log n)$ |
$O(1)$ |
$O(log n)$ |
$O(log n_1 + log n_2)$ |
可以看出，在合并操作时，左偏树更胜一筹
那么左偏树又是如何高效地实现合并两棵左偏树的呢？下面我们将对此展开探讨。
左偏树的概念 & 性质
在具体探讨左偏树之前，我们先来看一下它的几条概念与性质
概念篇
对于左偏树的任意一个节点，只要它的左子树或右子树为空，则称它是一个外节点
对于左偏树的任意节点$s$，到它的子节点中，距离它最近的一个外节点经过的边数称为它的距离，记为$far[x]$。特别地，外节点的距离为0，空节点得距离为-1
性质篇
堆性质：左偏树的每一个节点均满足堆的性质，即每一个点的权值（不是距离）必须大于或小于它的每一个子节点。
左偏性质：对于左偏树中的任意节点，满足其左子树的距离大于其右子树的距离，即$far[left] > far[right]$。
对于左偏树的任意节点，满足它的左右子树（如果有的话）均为左偏树。
左偏树的节点距离总是满足$far[s] = far[right(s)] + 1$， 即一个节点的距离等于其右节点的距离+1
所有根节点距离为$k$的左偏树中，节点最少的是满二叉树，且节点数为$2^{k+1}−1$。
根据上面的性质我们也可以推出左偏树的定义：左偏树是具有左偏性质的堆状二叉树。
左偏树的操作
左偏树一共有3种操作，分别是合并，插入，删除。
下面我们就来探讨基于大根堆的左偏树的这几种操作（小根堆请读者自行脑补）
Merge
为什么最先讨论合并操作？？因为它是左偏树最基础的操作。插入与删除两种操作都离不开它。
左偏树的操作的原理是把一颗根节点较小的左偏树插入一颗根节点较大的左偏树中。
因此，函数的两个参数为两颗子树的根节点。
在合并，我们需要特别判断是否存在空树，如果有的话，直接合并即可。
如果没有的话，我们就要确定应该使用哪一个节点做为根节点。所以我们会将两个根节点的权值相比较，用权值大的节点作为根节点。
之后我们将根节点的右子树与之前比较的另一个节点合并，并比较合并后左右子树的大小。如果右子树偏大的话，就将左右子树交换。
最后，运用性质4计算一下根节点的距离即可。
代码如下：
int merge(int x , int y){
if(!x || !y){
return x + y ;
}
if(node[x].dis > node[y].dis){
swap(x , y);
}
node[x].right = merge(node[x].right , y);
node[node[x].right].pre = x;
if(node[node[x].left].far < node[node[x].right].far){
swap(node[x].left , node[x].right);
}
node[x].far = node[node[x].right].far + 1;
return x;
}
|
push
现在我们已经可以以一只$log$的时间复杂度合并两颗左偏树了
so……
插入一个节点就等于将被插入的节点作为一颗子树合并啊
直接套上边模板吧
pop
删除操作就相当于合并被删除点的两棵子树。
当然，在此之前，我们要先把被删除的点续掉
代码如下
int pop(int x){
int l = node[x].left;
int r = node[x].right;
node[x].dis = -1;
node[l].pre = l;
node[r].pre = r;
node[x].pre = merge(l , r);
}
|
附件[左偏树模板]
代码描述 ：见洛谷P3337
源代码：
#include<iostream>
#include<algorithm>
#define N 100001
#define DEBUG(x) cout << "----------------------" << endl;\
cout << "x" << endl;\
cout << "----------------------" << endl;\
using namespace std;
struct Node{
int pre;
int dis;
int far;
int left;
int right;
}node[N];
int find(int root){
if(node[root].pre == root){
return root;
}
else{
return node[root].pre = find(node[root].pre);
}
}
int merge(int x , int y){
if(!x || !y){
return x + y ;
}
if(node[x].dis > node[y].dis){
swap(x , y);
}
node[x].right = merge(node[x].right , y);
node[node[x].right].pre = x;
if(node[node[x].left].far < node[node[x].right].far){
swap(node[x].left , node[x].right);
}
node[x].far = node[node[x].right].far + 1;
return x;
}
void pop(int x){
int l = node[x].left;
int r = node[x].right;
node[x].dis = -1;
node[l].pre = l;
node[r].pre = r;
node[x].pre = merge(l , r);
}
int main(){
int read;
int n , m;
int a , b , c;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> read;
node[i].pre = i;
node[i].dis = read;
}
for(int i = 1; i <= m; i ++){
cin >> a;
if(a == 1){
cin >> b >> c;
if(node[b].dis == -1 || node[c].dis == -1){
continue;
}
b = find(b);
c = find(c);
if(b != c){
merge(b , c);
}
}
else{
cin >> b;
if(node[b].dis == -1){
cout << "-1" << endl;
}
else{
cout << node[b = find(b)].dis << endl;
pop(b);
}
}
}
return 0;
}
|
如果觉得这份模板不好记忆的话，作者还有一份更好记忆的
#include<iostream>
#include<cstdio>
#define N 1000001
#define DEBUG(x)\
cout << "--------------------------" << endl;\
cout << x << endl;\
cout << "--------------------------" << endl;
using namespace std;
struct Node{
int pre;
int left;
int right;
int dis;
int far;
#define pre(x) node[x].pre
#define left(x) node[x].left
#define right(x) node[x].right
#define dis(x) node[x].dis
#define far(x) node[x].far
}node[N];
int find(int root){
if(pre(root) == root){
return root;
}
else{
return pre(root) = find(pre(root));
}
}
int merge(int x , int y){
if(!x || !y){
return x + y;
}
if(dis(x) > dis(y) || dis(x) == dis(y) && x > y){
swap(x , y);
}
right(x) = merge(right(x) , y);
pre(right(x)) = x;
if(far(left(x)) < far(right(x))){
swap(left(x) , right(x));
}
far(x) = far(right(x)) + 1;
return x;
}
void pop(int root){
int l = left(root);
int r = right(root);
dis(root) = -1;
pre(l) = l;
pre(r) = r;
pre(root) = merge(l , r);
}
int main(){
int read;
int n , m;
int a , b , c;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> read;
node[i].pre = i;
node[i].dis = read;
}
for(int i = 1; i <= m; i ++){
cin >> a;
if(a == 1){
cin >> b >> c;
if(node[b].dis == -1 || node[c].dis == -1){
continue;
}
b = find(b);
c = find(c);
if(b != c){
merge(b , c);
}
}
else{
cin >> b;
if(node[b].dis == -1){
cout << "-1" << endl;
}
else{
cout << node[b = find(b)].dis << endl;
pop(b);
}
}
}
return 0;
}
|
THE END
