左偏树（可并堆）

· · 个人记录

link to cnblogs

入门

1. 基本要素

  1. 定义“外结点”表示左儿子或右儿子为空的结点

  2. 定义 dis_u 表示结点 u 到最近的一个“外结点”的距离

2. 基本性质及结论

  1. 左偏树本质为小根堆，满足一个结点的权值大于等于其左右儿子的权值

  2. 左偏树满足左偏的性质，即对于任意一个结点 u，满足 dis_{l_u}\ge dis_{r_u}

  3. 由于有 dis_{l_u}\ge dis_{r_u}，因此一定有 dis_u=dis_{r_u} + 1

  4. 定义有 n 个结点的左偏树的根为 rt，满足 dis_{rt} 是 \log n 级别的

  5. 一个 dis_{rt}=n 的左偏树，其结点数至少为 2^{n + 1} - 1（此时为满二叉树）

3. 基本操作

① 合并 (merge)

左偏树最关键的就在它的合并操作上

定义 merge(x,y) 为将以 x 和 y 为根的两颗左偏树进行合并

我们先来考虑一下普通的小根堆怎么合并

首先，如果有 val_x\le val_y，那么显然合并后的根为 x；为了方便，当有 val_x > val_y 时，交换 x, y

接着，我们将 y 与 x 的左右儿子中选择一个进行合并，即 merge(y, son_x)；用返回的根节点取代这个 x 的儿子的位置

重复上述操作，直到当 x 或 y 出现一个空节点时，我们返回 x+y（根节点）

这样合并，最坏情况下是 O(n) 的，因为每次合并的复杂度是两颗树的深度和

因此，我们需要优化，一种是每次随机选择左右儿子；另一种就是采用左偏树，能够每次都稳定在 O(\log n)

因为 dis_{ls} \ge dis_{rs}，我们每次合并都选择右儿子；而合并完后，为了保持左偏的性质，如果 dis_{ls}<dis_{rs}，我们就交换左右儿子

② 新增结点

将这个结点当成树，进行合并操作即可

③ 求最小值并删除

堆顶就是最小值；删除即将左右儿子合并即可

记得删除后要将原来的堆顶结点清空！

④ 求结点所在的树的根节点

我们可以记录每个结点的父亲，然后一直向上跳。但显然，这样的复杂度是不对的

我们考虑用路径压缩，直接指向根节点

在合并时，我们将 rt_x=rt_y=merge(x,y)

再删除时，我们要使 rt_{l_u}=rt_{r_u}=rt_{u}=merge(l_u, r_u)，因为之前有一些结点指向 u，所以我们 rt_u 也要指向 merge(l_u, r_u)

代码