可并堆(左偏树)学习笔记

为什么要学左偏树

有时候,某些题目要求我们合并两个堆。

合并两个堆,大家都知道可以用splay暴力启发式合并处理。很不幸的是,这玩意的复杂度是$O(nlog^2n)$的,在一些毒瘤题目专门考可并堆的题目中,是注定要被卡的。

可并堆系列算法可以很优雅的解决这系列的算法,她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。


什么是左偏树

正如她字面意思一样,是一颗向左“偏”的树。什么叫“向左偏”呢?我们知道,平衡树的时间复杂度比二叉查找树优秀,是因为平衡树的左右子树深度尽可能平衡以保证每次大小/2。在这里呢,我们左偏树故意让左子树比右子树大一点来维护平衡性。


左偏树咋写啊

左偏树是通过维护一个深度变量$dis[x]$来保证左孩子比右孩子略大的。$dis$的定义是:$dis[x]=min(dis[lson],dis[rson])$,考虑到我们的左偏树中每个节点都满足这个性质,易得:$dis[x]=dis[rson]+1$

以下内容默认左偏树为大根堆,小根堆请读者自行类比

Merge

明白$dis$的定义之后,左偏树就很好写了。假设我们现在要合并两颗左偏树,显然,新的树根一定是两棵树根权值较大的那个。然后我们把权值较大那棵树的树根作为新的树根,新的树的左孩子为权值较大的那棵树的左孩子,右孩子则递归合并另外那颗树与权值较大的树的右孩子。

代码大概长这样:

int Merge(int x,int y)//x,y为堆顶
{
    if(x==0 or y==0) return x+y;//若其中某颗子树为空则直接返回
    if(a[x]<a[y]) swap(x,y);//保证x的权值>y,方便接下来的讨论
    son[x][1]=Merge(son[x][1],y);//右孩子递归合并
    fa[son[x][0]]=fa[son[x][1]]=x;//设置左右孩子的fa
    if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]);//维护左偏性质
    dis[x]=dis[son[x][1]]+1;//维护dis
    return x;
}

Delete

左偏树作为一个堆,那自然要能删除堆顶元素。删除操作很好处理,我们把根去掉,然后Merge其孩子即可。
因为我们要对fa做路径压缩(如同并查集一样),我们这里必须把旧的根的fa设为新的根,以保证之后能正确的找到新的树的树根

void Delete(int x)//x为堆顶
{
    fa[son[x][0]]=fa[son[x][1]]=0;//重设孩子的fa
    fa[x]=Merge(son[x][0],son[x][1]);//Merge孩子并把旧根的fa设为新的根
}

有啥题目做啊

模板题:P3377 【模板】左偏树(可并堆
神题:P3273 SCOI2011棘手的操作

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注