可并堆

luckydrawbox · 2022-09-29 13:21:25 · 个人记录

变量

函数

代码

struct Mergeable_Heap{
    struct Node{
        int id,val,l,r,dist,em;
        bool operator < (Node x) const{
            return (val==x.val?id<x.id:val<x.val);
        }
    }a[N];
    Mergeable_Heap(){
        a[0].dist=0;
    }
    void insert(int x,int val){
        a[x].id=x;
        a[x].val=val;
        mfs.fa[x]=x;
        a[x].em=0;
    }
    int merge_heap(int x,int y){
        if(!x||!y)
            return x+y;
        if(a[y]<a[x])
            swap(x,y);
        a[x].r=merge_heap(a[x].r,y);
        if(a[a[x].l].dist<a[a[x].r].dist)
            swap(a[x].l,a[x].r);
        a[x].dist=a[a[x].r].dist+1;
        return x;
    }
    void merge(int x,int y){
        if(a[x].em||a[y].em)
            return;
        x=mfs.get(x);
        y=mfs.get(y);
        if(x!=y)
            mfs.fa[x]=mfs.fa[y]=merge_heap(x,y);
    }
    bool remove(int x){
        if(a[x].em)
            return 0;
        x=mfs.get(x);
        a[x].em=1;
        mfs.fa[a[x].l]=mfs.fa[a[x].r]=mfs.fa[x]=merge_heap(a[x].l,a[x].r);
        a[x].l=a[x].r=a[x].dist=0;
        return 1;
    }
    int top(int x){
        if(a[x].em)
            return -1;
        x=mfs.get(x);
        return a[x].val;
    }
}h;