左偏树

Merge 里大根堆 \(val_x < val_y\)，小根堆 \(val_x > val_y\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
namespace LeftistTree
{
    int N,rt[MAX],lson[MAX],rson[MAX],val[MAX],dis[MAX];
    inline void init() {for(int i=1;i<=N;++i) rt[i]=i;}
    int find(int x) {return x==rt[x]?x:rt[x]=find(rt[x]);}
    int Merge(int x,int y)
    {
        if(!x||!y) return x|y;
        if(val[x]==val[y]?x>y:val[x]<val[y]) Swp(x,y);
        rson[x]=Merge(rson[x],y);
        if(dis[lson[x]]<dis[rson[x]]) Swp(lson[x],rson[x]);
        rt[lson[x]]=rt[rson[x]]=rt[x]=x,dis[x]=dis[rson[x]]+1;
        return x;
    }
    inline void Pop(int x) {x=find(x),rt[x]=rt[lson[x]]=rt[rson[x]]=Merge(lson[x],rson[x]);}
    inline void Extract(int x)
    {
        int L=lson[x],R=rson[x];
        rt[L]=L,rt[R]=R,lson[x]=rson[x]=dis[x]=0,Merge(Merge(L,R),find(x));
    }
    inline int Build()
    {
        queue<int> q; int x,y;
        for(int i=1;i<=N;++i) q.emplace(i);
        while(q.size()>1) x=q.front(),q.pop(),y=q.front(),q.pop(),q.emplace(Merge(x,y));
        return q.front();
    }
}