【左偏树】【可并堆】

Mathison · 2018-10-06 21:26:40 · 个人记录

今天学习了新的数据结构

左偏树（可并堆）

我们使用\text{priority\_queue}可以等价一个大（小）根堆

但是当遇到两个堆要合并的操作就很麻烦（一个一个\text{pop()}再一个一个\text{push()}）

这时候我们就要手写左偏树（可并堆）

【定义】

从名字上看，它是一棵树。其实它还是一棵二叉树。它的节点上存4个值：左、右子树的地址，权值，距离。

权值就是堆里面的值。距离表示这个节点到它子树里面最近的叶子节点的距离。叶子节点距离为0。

【性质】

左偏树的四个性质（以小根堆为例）：

性质一：节点的权值小于等于它左右儿子的权值。（小根堆性质）

性质二：节点的左儿子的距离不小于右儿子的距离。

性质三：节点的距离等于右儿子的距离+1。

性质四：一个n个节点的左偏树距离最大为log(n+1)-1

【操作】

一.合并

既然叫可并堆当然最重要的是合并操作了

我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树和B了。
合并了A的右子树和B之后，A的右子树的距离可能会变大，当A的右子树的距离大于A的左子树的距离时，性质二会被破坏。在这种情况下，我们只须要交换A的右子树和左子树。
而且因为A的右子树的距离可能会变，所以要更新A的距离=右儿子距离+1。这样就合并完了。

int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(val[x]>val[y]||(val[x]==val[y]&&x>y)) swap(x,y);//1.
    son[x][1]=merge(son[x][1],y);//1.
    fa[son[x][1]]=x;//1.
    if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]);//2.
    dis[x]=dis[son[x][1]]+1;//3.
    return x;
}

二、插入

把一个点和一棵树合并起来。
（因为其中一棵树只有一个节点，所以插入的效率是O(\log n)）

三、删除最小/大点

权值赋成-1
合并两个节点的儿子

（因为只合并了一次，所以效率也是O(\log n)。）

【代码】（以小根堆为例）（大小根堆区别就在一个符号上）

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,son[N][2],val[N],dis[N],fa[N];
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(val[x]>val[y]||(val[x]==val[y]&&x>y)) swap(x,y);
    son[x][1]=merge(son[x][1],y);
    fa[son[x][1]]=x;
    if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]);
    dis[x]=dis[son[x][1]]+1;
    return x;
}
int find(int x)//不用路径压缩,不赋初值，所以他祖先没有父亲(为0 
{
    while(fa[x]) x=fa[x];
    return x;
}
void pop(int x)
{
    val[x]=-1;
    fa[son[x][0]]=fa[son[x][1]]=0;
    merge(son[x][0],son[x][1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    dis[0]=-1;
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<=m;i++)
    {
        int pos;
        scanf("%d",&pos);
        if(pos==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y||val[x]==-1||val[y]==-1) continue;
            merge(find(x),find(y));
        }
        if(pos==2)
        {
            int x;
            scanf("%d",&x);
            if(val[x]==-1) puts("-1");
            else
            {
                int xx=find(x);
                printf("%d\n",val[xx]);
                pop(xx);
            }
        }
    }
    return 0;
}

【左偏树 】【可并堆】