二叉堆++

盐盐

2023-11-30

数据结构

我们知道，二叉堆有一些很好的性质，比如可以 $\Theta(1)$ 获取最值， $\Theta(n)$ 建树， $\Theta(logn)$ 维护。但是在一些更复杂的操作的时候，总是显得有些力不从心。
比如这道 Monkey King，猴子每次打架的时候需要对两个大根堆进行合并。而使用普通的方法，每次合并的时候复杂度的量级为线性，容易超时。因此就需要特殊性质的堆来解决。典型的有配对堆和左偏树。

左偏树

定义

以下来自 OI Wiki

左偏树是一种可并堆，具有堆的性质，并且可以快速合并。
外节点为子节点数小于两个的节点，定义一个节点的 $dist$ 为其到子树中最近的外节点所经过的边的数量。空节点的 $dist$ 为 0。
左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的 $dist$ 都大于等于右儿子的 $dist$ 。

因此，左偏树每个节点的 $dist$ 都等于其右儿子的 $dist$ 加一。

操作

合并
见下，由于根的 $dist$ 不会超过 $\lfloor log_2(n+1) \rfloor$ (因为二叉树的前 n-1 是满二叉树)，而递归每次使 $dist$ 减一，因此合并的复杂度为 $log_2m+log_2n$
插入
等同于合并一个节点和堆
删除根
合并根的左右节点
删除任意节点
合并左右儿子，向上更新 $dist$ ，交换左右儿子以满足性质。复杂度 $\Theta(logn)$

细节

由于左偏树的性质，有可能退化为链，这种情况下在左偏树中寻找根节点有点困难（可能会被卡），要配合并查集一起食用

模板

#define ch(x, side) (tr[x].ch[side])
struct NODE{
    int fa,ch[2],v,dist;
} tr[N];
int &rson(int x){
    return tr[tr].dist>tr[rs(x)].dist?rs(x):ls(x);
}
int find(int x){
    return tr[x].fa==x?x:(tr[x].fa=find(tr[x].fa));
}

int merge(int x,int y){
    if(!x||!y) return x|y;
    if(val(x)>val(y)||(val(x)==val(y)&&x>y)) swap(x,y);
    // 下面是静态右儿子的做法
    // tr[rs(x)=merge(rs(x),y)].fa=x;
    // if(dist(ls(x))<dist(rs(x))){
    //     swap(ls(x),rs(x));
    // }
    // dist(x)=dist(rs(x))+1;
    // return x;
    int& rs_ref = rson(x);
    tr[rs_ref = merge(rs_ref, y)].fa = x;
    dist(x) = dist(rson(x)) + 1;
    return x;
}
void pushup(int x){
    if(!x) return;
    if(dist(x)!=dist(rson(x))+1){
        dist(x)=dist(rson(x))+1;
        pushup(tr[x].fa);
    }
}
void delete(int x){
    int y=merge(ch(x,0), ch(x,1));
    tr[y].fa=tr[x].fa;
    ch(tr[x].fa, ch(tr[x].fa,1)==x)=y;
    pushup(tr[x].fa);
}

碎碎念

被这道题卡了好久

最后发现，我根本不会并查集
为什么这么说呢？大家可能都清楚并查集的用处，路径压缩，启发式合并，菊花图，但是事实上并查集有很多细节
比如说这道题，带删除的，就会使并查集的路径压缩失效。那怎么处理呢？就是把被删除的节点的父亲指向自己的儿子，也就是回溯

这道题还有很多细节值得推敲，比如把dist置0作判断是否存在的条件，merge前先检查
~~本来写的是动态计算右儿子的做法，但是最后觉得不好调试就改了~~现在改了