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

为什么要学左偏树

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

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

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

什么是左偏树

正如她字面意思一样，是一颗向左“偏”的树。

什么叫“向左偏”呢？我们知道，平衡树的时间复杂度比普通的二叉查找树优秀，是因为平衡树的左右子树深度尽可能平衡以保证每次大小/2。

在这里呢，我们左偏树故意让左子树比右子树大一点来维护平衡性。

左偏树咋写啊

左偏树是通过维护一个深度变量$dis[x]$来保证左孩子比右孩子略大的。

$dis$的定义是：$dis[x]=min(dis[lson],dis[rson])$，考虑到我们的左偏树中每个节点都满足这个性质，易得：$dis[x]=dis[rson]+1$

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

Merge

明白$dis$的定义之后，左偏树就很好写了。

假设我们现在要合并两颗左偏树，显然，新的树根一定是两棵树根权值较大的那个。然后我们把权值较大那棵树的树根作为新的树根，新的树的左孩子为权值较大的那棵树的左孩子，右孩子则递归合并另外那颗树与权值较大的树的右孩子。

代码大概长这样：

1
2
3
4
5
6
7
8
9
10

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设为新的根，以保证之后能正确的找到新的树的树根

1
2
3
4
5

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棘手的操作