左偏树 | Sherlock小蒟蒻

前言：

前几天学习高级数据结构，现在准备复习…

左偏树杂谈：

左偏树是一种可并堆。
对于一般的而言，我们可以很容易地想到一种时间复杂度为 O（n ) 的
算法合并两个堆。看样子可以接受，但是如果要合并一万次，十万次的话，总的时间复杂度却很难让人接受，因此左偏树应运而生。
优先队列也能算是可并堆，在优先队列中插入一个数，时间复杂度应该是 O（log2n) （百度上说的本人没有证明），但是优先队列不支持合并。
而左偏树，是一种可并堆的实现，能够在时间复杂度为 O（loga + logb) 的情况下合并两个堆。
现在我们着重讲讲左偏树的性质与合并时的算法

左偏树性质：

左偏树是一棵二叉树，它具有二叉树的性质
比如说一个节点的键值小于等于它两个儿子的键值，因而这棵树的根一定是整个堆中最小的数，我们可以在 O（1）的时间复杂度下取出最小值
它的节点有一个左指针和一个右指针，还有这个节点的键值，还有距离。键值很好理解，而左偏树的重点是它的距离，合并删除的实现也和距离分不开，也因距离而得名为左偏树（口糊）
我们这样定义距离：（划重点！！！
如果一个节点，它的左儿子或者右儿子为空，那么我们称这个节点为外节点，换句话说，称为外节点的点的儿子只有一个或者没有（真可伶
而左偏树的精髓–距离，指的是该节点 i 到它最近的外节点所经过的边数。如果这个点为外界点，那么这个点的距离为 0，如果这个点为空，那么这个点的距离为 -1 。
我们称一棵左偏树的距离为这棵树根节点的距离。

左偏性质：

左偏性质导致该数据类型叫做左偏树。
即该节点左孩子的距离要不小于右孩子的距离
我们可以得到，节点 i 的距离等于它右儿子的距离加 1 ，所以我们规定外节点的距离为0空节点距离为 -1
而在进行合并和删除可并堆的时候，我们一定要注意维护左偏性质

距离与节点的关系

一棵左偏树的距离为 k ，那么这棵左偏树的节点数最少有 2^k+1-1（我觉得用极端法就可以证明
还有一点我不会证明的（我也没去证明…）若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。
一棵 N 个节点左偏树距离最多为 log（N+1）-1.

我也想要插入图片！！！

左偏树模板:

题目描述

如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）

操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数，表示一条操作，格式如下：

操作1 ： 1 x y

操作2 ： 2 x

输出格式：

输出包含若干行整数，分别依次对应每一个操作2所得的结果。

输入输出样例:

我觉得我们对左偏树一些基本性质的讲解已经很清楚了，我们现在来看一下怎么实现代码…

初始化节点每个节点有四个元素：左儿子右儿子键值距离
我们用并查集来找这一个堆的祖宗…注意**不
能路径压缩**因为如果这个堆的祖先被删去了，对于这个堆你就找不到祖先了（大哭
现在讲讲合并操作（我觉得我应该找个图来的
如果一棵树为空，那么我们只需要返回另一棵树，像这样

1	if(!x\|\|!y) return x+y;

如果两棵树为非空，我们假设 A 的根节点小于等于 B 的根节点（否则交换 A ， B
把 A 的根节点作为新树 C 的根节点，再合并 A 的右子树和 B
合并 A 的右子树和 B 后，A 的右子树的距离可能会变大，当合并后 A 的右儿子距离大于左儿子距离时，我们只需要交换左儿子和右儿子即满足了左偏树的性质
最后，我们更新 A 的距离，即 dis( A )=dis( right(A) )+1;
不难发现，合并后新的树也满足左偏性质
我们贴一下代码

  	inline int merge(int x,int y){
 			if(!x||!y) return x+y;
  		if(a[x].value>a[y].value||(a[x].value==a[y].value&&x>y)) swap(x,y);
  		int &ls=a[x].l,&rs=a[x].r;
  		rs=merge(rs,y);
  		a[rs].fa=x;
   	if(a[rs].dis>a[ls].dis) swap(ls,rs);
   	a[x].dis=a[rs].dis+1;
   	return x;
}

合并操作之后我们再讲讲删除节点
其实删除操作很简单，如果我们要删除节点为 X ，只需要把 X 节点的信息清空，再把 X 的左儿子和右儿子进行合并即可。

我们贴一下代码

inline void del(int x){
    int ls=a[x].l,rs=a[x].r;
    a[x].value=-1;
       a[ls].fa=a[rs].fa=0;
       merge(ls,rs);
}

这样我们讲完了左偏树的基本操作，现在贴出这道模板题的AC代码

AC代码氧气优化152ms

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

const int N=100010;
int n,m;
int x,y;
struct node{
    int l,r,value,fa,dis;
}a[N];

//inline void swap(int &a,int &b) {a^=b^=a^=b;}

inline int find(int x){return a[x].fa?find(a[x].fa):x;}

inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(a[x].value>a[y].value||(a[x].value==a[y].value&&x>y)) swap(x,y);
    int &ls=a[x].l,&rs=a[x].r;
    rs=merge(rs,y);
    a[rs].fa=x;
    if(a[rs].dis>a[ls].dis) swap(ls,rs);
    a[x].dis=a[rs].dis+1;
    return x;
}

inline void del(int x){
    int ls=a[x].l,rs=a[x].r;
    a[x].value=-1;
    a[ls].fa=a[rs].fa=0;
    merge(ls,rs);
}

int main(){
    scanf("%d%d",&n,&m);
    a[0].dis=-1;
    rep(i,1,n) scanf("%d",&a[i].value);
    while(m--){
        int type;
        scanf("%d",&type);
        switch(type){
            case 1:{
                scanf("%d%d",&x,&y);
                if(a[x].value!=-1&&a[y].value!=-1){
                    int p=find(x),q=find(y);
                    if(p!=q) merge(p,q);
                }
                break;
            }
            case 2:{
                scanf("%d",&x);
                if(a[x].value==-1) printf("-1\n");
                else {
                    int p=find(x);
                    printf("%d\n",a[p].value);
                    del(p); 
                    break;
                }
            }
        }
    }
    return 0;
}

我觉得我讲的已经很详细了，现在我们来进行实战

Monkey King：

题目描述：

一开始有n只孤独的猴子，然后他们要打m次架，每次打架呢，都会拉出自己朋友最牛叉的出来跟别人打，打完之后他的朋友的战斗力就会减半，每次打完架双方所有人就会成为朋友（正所谓不打不相识o(∩_∩)o ）。问每次打完架之后那俩猴子最牛叉的朋友战斗力还有多少，若朋友打架就输出-1.

输入输出格式：

暂不支持英文翻译….

解题分析：

很容易发现这道题需要我们合并两个堆…
但是每个堆合并之后的根的键值会变化…
我们使用大根堆，以便找到堆中最大的数来打架…然后考虑左偏树…
合并的操作上面的模板题我们已经探讨过了，但是每个合并之前的左偏树的根该如何维护其性质呢
合并之后的两个堆的根不一定是原先两个堆的根中的一个（因为战斗力会下降…
所以我们应该把要合并的两堆的根先删去，键值除以二，得到合并后的键值，再插入(即合并只有一个数的堆和删去根后的堆），再合并两个经过操作的堆，这时候的根节点即两堆猴子打完架后战斗力最强的猴子…
这样我们只需要合并操作与删除操作，再注意一些细节，就容易就过了…
目前也只找到一道用左偏树写的题…
贴出代码…

AC代码氧气优化176ms

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define max(a,b) (a>b?a:b)

using namespace std;

int n,m,x,y;
struct node{
    int l,r,dis,value,fa;
}a[100010];

inline int find(int x){return a[x].fa!=x?find(a[x].fa):x;}

inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(a[x].value<a[y].value) swap(x,y);
    a[x].r=merge(a[x].r,y);
    a[a[x].r].fa=x;
    if(a[a[x].l].dis<a[a[x].r].dis) swap(a[x].r,a[x].l);
    if(!a[x].r)a[x].dis=0;
    else a[x].dis=a[a[x].r].dis+1;
    return x;
}

inline int del(int x){
    int ls=a[x].l,rs=a[x].r;
    a[x].l=a[x].r=a[x].dis=0;a[ls].fa=ls;a[rs].fa=rs;
    return merge(ls,rs);
}

int main(){
    while(scanf("%d",&n)!=EOF){
        a[0].dis=-1;
        rep(i,1,n) {
            scanf("%d",&a[i].value);
            a[i].fa=i;
            a[i].dis=a[i].r=a[i].l=0;
        }
        scanf("%d",&m);
        rep(i,1,m){
            scanf("%d%d",&x,&y);
            int p=find(x),q=find(y);
            if(p==q) {
                printf("-1\n");continue;
            }
            a[p].value/=2;a[q].value/=2;
            int lr=del(p),rr=del(q);
            lr=merge(lr,p);rr=merge(rr,q);
            lr=merge(lr,rr);
            printf("%d\n",a[lr].value);
        }
    }
    return 0;
}

本文完，欢迎指正…（我太弱了…

联系qq： 953559040

微博： IncinblePan

洛谷： SherlockPan

前言：