[算法] 可并堆

hyh集训队论文

左偏树(小根堆)：

int merge(int x, int y) {
    if(!x) return y;
    if(!y) return x;
    if(v[x]>v[y]) swap(x,y);
    rs[x]=merge(rs[x],y);
    if(dis[rs[x]>dis[ls[x]]]) swap(ls[x],rs[x]);
    if(!rs[x]) dis[x]=0;
    else dis[x]=dis[rs[x]]+1;
    return x;
}

int pop(int x) {
    int l=ls[x],r=rs[x];
    ls[x]=rs[x]=dis[x]=0;
    return merge(l,r);
}

//取堆顶直接访问v[x]即可

斜堆：

//需要先对结点编号？没太懂

int merge(int x, int y) {
    if(!x || !y) return x+y;
    if(v[x]>v[y]) swap(x,y);
    rs[x]=merge(rs[x],y);
    swap(ls[x],rs[x]);
    return x;
}

int pop(int x) {
    return merge(ls[x],rs[x]);
}