合并 merge#

合并是左偏树的的核心操作。

合并两个堆时，由于要满足堆性质，先取值较大的那个根作为合并后堆的根节点。

然后将根的左儿子作为合并后堆的左儿子，递归合并其右儿子与另一个堆，作为合并后的堆的右儿子。

为了满足左偏树的性质，若合并完后左儿子的 $dist$ 小于右儿子的 $dist$，就交换左右儿子。

1
void merge(int x,int y) {
2
  if(!x||!y) return x+y;//若一个堆为空，返回另一个堆
3
  if(w[x]<w[y]) swap(x,y);
4
  rson[x]=merge(rson[x],y);
5
  if(dist[lson[x]]<dist[rson[x]])
6
    swap(lson[x],rson[x]);
7
  dist[x]=dist[rson[x]]+1;//更新 dist
8
  return x;
9
}

由于左偏性质，每递归一层，其中一个堆根节点的 $dist$ 就会减小 $1$，而一棵有 $n$ 个节点的二叉树，根的 $dist$ 不超过 $\left\lceil\log (n+1)\right\rceil$，所以合并两个大小分别为 $n$ 和 $m$ 的堆复杂度是 $O(\log n+\log m)$。

插入节点 insert#

单个节点也可以视为一个堆，合并即可。

删除根 pop#

合并根的左右儿子即可。

删除节点 erase#

先将左右儿子合并，然后自底向上更新 $dist$，不满足左偏性质时交换左右儿子，当 $dist$ 无需更新时结束递归。

1
void pushup(int x) {
2
  if(!x) return;
3
  if(dist[x]!=dist[rson[x]]+1) {
4
    dist[x]=dist[rson[x]]+1
5
    pushup(fa[x]);
6
  }
7
}
8
void erase(int x) {
9
  int y=merge(lson[x],rson[x]);
10
  fa[y]=fa[x];
11
  if(lson[fa[x]]==x)
12
    lson[fa[x]]=y;
13
  else rson[fa[x]]=y;
14
  pushup(fa[y]);
15
}