左偏树

左偏树的结构

除了维护堆性质之外，左偏树还要在每个节点多维护一个 $s$ 值。$s$ 值定义如下：

• 外结点是左儿子或右儿子为空的节点，定义一个外结点的 $s$ 值为 $1$。
• 一个不是外结点的节点的 $s$ 值为其到子树最近的外结点的距离 $+1$。
• 空节点的 $s$ 为 $0$。（如果这样操作，则在左偏树中额外标记出空节点，可以发现 $s$ 值实际上代表到子树中最近的空节点的距离）

左偏树对 $s$ 有要求：每个节点左儿子的 $s$ 值都大于等于右儿子的 $s$ 值。因此，左偏树每个节点的 $s$ 值都等于其右儿子的 $s$ 值 $+1$。如何证明？考虑动态规划的思想，$s(fa)=\min (s(lc),s(rc))+1=s(rc)+1$。

左偏树与堆的不同：不仅具有堆的性质，而且形态上左偏，由于不是完全二叉树，所以左偏树的深度没有保证。然而，根的 $s$ 值不超过 $[\log n+1]$。

左偏树的操作

左偏树的核心操作在于合并。

• 插入：视为与只有一个元素的左偏树合并。
• 删除根（pop_front）：将左右子树合并。
• 删除任意节点：将左右儿子合并，更新 $s$ 值。

1
2
3
4
5
6
7
8
9
10
11
12
13

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);//这里维护的是小根堆，因此需要保证主体根节点大于被合并上来的堆的根节点
	fa[ch[x][1]=Merge(ch[x][1],y)]=x;//将主体堆的右子树和被合并的堆的右子树合并，更新父节点信息
	if (dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);//维护左偏树性质
	dis[x]=dis[ch[x][1]]+1;//维护s值
    return x;
}
void pop(int &x){
	val[x]=-1;//设为空节点
	fa[ch[x][0]]=fa[ch[x][1]]=0;
	Merge(ch[x][0],ch[x][1]);
}