左偏树是一种可并堆（一系列的堆），支持以下操作：
-
删除一个堆的最值。
-
查询一个堆的最值。
-
新建一个堆，只包含一个元素。
-
合并两个堆。这个复杂度是 \(O(\log)\) 的。
左偏树是一颗二叉树。定义 “外结点” 为儿子数量不等于 \(2\) 的结点，定义每个结点的 \(dist\) 为该结点到最近的外结点的距离。
左偏树满足对于每个节点，左儿子的 \(dist>\) 右儿子的 \(dist\)。
左偏树满足堆的性质，即一个结点是它子树内的最值。
对于 2 操作，输出一个左偏树的根即可。
对于 3 操作，显然很简单。
如果我们实现了 4，则 1 就只需要合并根的左右儿子，然后删除根即可。
如何实现 4 ？我们观察到一个性质。如果左偏树从根出发一直向右走，最多走 \(\log n\) 步，就会到达一个没有子结点的结点 \(x\)。
证明：假设还能继续往下走。注意到 \(x\) 已经是最右的结点了，所以为了使它的祖先们满足左 \(dist>\) 右 \(dist\)，如果截取深度为 \(1\sim dth[x]\) 的这一段，必构成满二叉树。满二叉树结点个数是 \(2\) 的幂，所以 \(d[x]\le \log n\)。
根据这个结论，可以设计出 \(O(\log n)\) 的合并堆算法：
-
初始有两颗左偏树 \(h1,h2\)，不妨 \(h1\) 的根优于 \(h2\)。
-
合并 \(h1\) 右节点的子树 和 \(h2\)，将合并出来的左偏树作为 \(h1\) 的右儿子。
-
如果此时 \(h1\) 右儿子的 \(dist\) 大于左儿子，交换左右儿子。