左偏树学习笔记

发布于 2018-05-19  238 次阅读


定义

大家都知道优先队列吧。
有时候我们需要合并优先队列,反正我们不能重新插入吧,我们就需要一种神奇的数据结构--可并堆

可并堆可以支持在$O(NlogN)$下进行插入,删除,合并,求极值。
在OI选手中,实现可并堆的最好方法是左偏树
那么左偏树是递归定义的,它与二叉堆不同,他不是一棵完全二叉树。
左偏树中的重要定义是NPL-表示该结点到最近的外部结点的位置。
满足要求 堆的要求+做结点的NPL一定不小于有结点的NPL
得到$ NPL(i) = NPL(i.right) + 1 $ $ max{NPL} < log(N+1) $
现在我们可以发现,这个堆大部分时候是向左偏的,所以说保证复杂度的是它的右链,所以所有操作 都被放到右链上 。

操作

对于小根堆H1和H2的合并(小根堆)
如果$ H1==NULL $或$ H2==NULL $那就$ return H1+H2 $
对于合并后的$ H1 $,如果左右子树的$ Npl $破坏规则,直接交换左右子树
以上反之亦然
注意一下找父亲过程要路径压缩一下,不然会被卡成 $O(n)$。

代码

左偏树(可并堆)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define lc (ch[x][0])
#define se second
#define U unsigned
#define rc (ch[x][1])
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100000+5;
int ch[MAXN][2],dis[MAXN],son[MAXN][2],f[MAXN],val[MAXN];

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline int merge(int x,int y){
    if(!x || !y) return x + y;
    if(val[x] > val[y] || (val[x] == val[y] && x > y)) std::swap(x,y);
    rc = merge(rc,y);if(dis[lc] < dis[rc]) std::swap(lc,rc);
    f[lc] = f[rc] = f[x] = x;dis[x] = dis[rc] + 1;return x;
}

inline void del(int x){
    val[x] = -1;f[lc] = lc;f[rc] = rc;
    f[x] = merge(lc,rc);
}

int N,M;

int main(){
    scanf("%d%d",&N,&M);dis[0] = -1;
    FOR(i,1,N) f[i] = i,scanf("%d",val+i);
    while(M--){
        int opt,x,y;scanf("%d%d",&opt,&x);
        // DEBUG(M);
        if(opt == 1){
            scanf("%d",&y);
            if(val[x] == -1 || val[y] == -1) continue;
            int fx = find(x),fy = find(y);
            if(fx != fy) f[fx] = f[fy] = merge(fx,fy);
        }
        else{
            if(val[x] == -1) puts("-1");
            else printf("%d\n",val[find(x)]),del(find(x));
        }
    }
    return 0;
}


一个OIer。