左偏树 学习笔记【左偏树】【可并堆】

点击量：174

一、什么是左偏树

1.左偏树简介

    左偏树是一棵二叉树。左偏树顾名思义就是往左偏的树，这样方便合并。为什么方便合并呢？我们把要合并的另一棵树与左偏树比较小的右侧合并，就能尽可能让二叉树+堆保持平衡，从而达到\(O(\log n)\)的操作复杂度。

2.左偏树的维护

    因为左偏树左偏的性质，所以它可以完成合并。那么怎样维护左偏呢？在合并的过程中，会有回溯的过程。在回溯过程中可以调整左右孩子，使得左儿子的距离不小于右儿子的距离。距离定义为这个节点到子树中最浅的没有左儿子或没有右儿子的节点所经过的边数。

3.插入删除操作

    既然它是个堆，就要能实现插入和删除最值。插入就是新建一个节点作为一棵左偏树，和要插入的左偏树进行合并。删除最值也好办，因为最值就在堆顶，所以删除堆顶就可以了。为了节省操作，我们还是用合并来实现，只要把根节点的左儿子和右儿子合并就完成了删除操作。

二、合并

    说了这么多，合并操作怎么实现呢？在左偏树中，合并当然是对右子树和新树进行合并。同时，为了维护堆性质，将右子树的根定为原右子树和新树中根节点较小的那个，然后将较大的那个与此时新右子树的右子树合并。（貌似有点像fhq_treap?）在回溯的过程中更新距离，如果发现一个节点儿子的个数少于2，那么它的距离为\(0\)；如果一个节点左儿子的距离小于右儿子的距离，就交换左右儿子，但是不打标记，因为不是区间反转，只用交换就可以了。此时左儿子的距离一定不小于右儿子的，那么就把自己的距离更新为右儿子的距离+1。

    这样存每个节点的位置，在合并两个堆时通过访问的节点去找它的父亲节点，把两个根合并就可以了。如果一个点被删除，那么就先合并它的左右儿子，接着把它指向的位置值变为-1，表明这个点已经被删除，之后再访问到-1就说明不存在这个点，直接输出-1。（luoguP3377）

三、Code

#include<cstdio>
#include<cstring>//左偏树
#include<map>
using std::map;
map<int,int> app;
struct node
{
    int key,num,dis;
    node *ls,*rs,*fa;
    node(int key,int num)
    {
        this->key=key;
        this->num=num;
        dis=0;
        ls=NULL;
        rs=NULL;
        fa=NULL;
    }
    node()
    {
        ls=NULL;
        rs=NULL;
    }
    friend bool operator <(node a,node b)
    {
        if(a.key!=b.key)
            return a.key<b.key;
        return a.num<b.num;
    }
    void maintain()
    {
        if(ls)
            ls->fa=this;
        if(rs)
            rs->fa=this;
        if((rs&&!ls)||(ls&&rs&&ls->dis<rs->dis))
        {
            node *tmp=rs;
            rs=ls;
            ls=tmp;
        }
        if(!ls||!rs)
            dis=0;
        else
            dis=rs->dis+1;
        return;
    }
    node *getfa()
    {
        if(!fa)
            return this;
        return fa->getfa();
    }
}*rt[100010];
node *Merge(node *a,node *b)
{
    if(!a||!b)
        return a?a:b;
    if((*a)<(*b))
    {
        a->rs=Merge(a->rs,b);
        a->maintain();
        return a;
    }
    b->ls=Merge(a,b->ls);
    b->maintain();
    return b;
}
int main()
{
    int n,m,op,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        rt[i]=new node(u,app[u]+1);
        app[u]++;
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&u,&v);
            if(rt[u]->key==-1||rt[v]->key==-1)
                continue;
            node *a=rt[u]->getfa();
            node *b=rt[v]->getfa();
            a=Merge(a,b);
            a->fa=NULL;
        }
        else
        {
            scanf("%d",&u);
            node *a=rt[u]->getfa();
            printf("%d\n",a->key);
            if(a->key==-1)
                continue;
            a->key=-1;
            a->fa=NULL;
            a=Merge(a->ls,a->rs);
            if(a)
                a->fa=NULL;
        }
    }
    return 0;
}