左偏树
左偏树是一种可并堆，它在维护元素关键值的同时，还维护了一个“距离”，让它左边的比重更大（“左偏”之所在），以此保证对左偏树修改后能快速回复成堆。
距离
外结点：一个节点 $u$ 被称为外结点当且仅当 $u$ 的左子树或右子树是空的。
距离：结点 $u$ 的距离 $\mathrm{dist}(u)$ 是它与子树中外结点距离的最小值。由于其左偏性质（见下），一个点的距离其实就是一直往右直到空的长度，因此有 $\mathrm{dist}(u)=\mathrm{dist}\left(\text{right son}(u)\right)+1$ 。
性质和定理
左偏树依赖堆性质和左偏性质，
- 堆性质：结点 $u$ 的关键值小于等于其子节点的关键值；
- 左偏性质：左儿子距离大于等于右儿子距离。
除此之外左偏树的距离和结点数有一些关系，这些关系可用于证明复杂度。
引理 1：一个左偏树的距离若为定值，则最小的左偏树是完全二叉树。
证明：距离为定值，则右子树距离确定，又要满足最小，则左子树的距离等于右儿子距离，递归下去就可知其为完全二叉树。
定理 1：若左偏树的距离为 $k$ ，则它至少有 $2^{k+1}-1$ 个结点。
证明：由引理 1 可知最少的情况是深度为 $k$ 的完全二叉树。
性质 3：由定理 1 可得，对于一棵 $n$ 个结点的左偏树，其距离最大为 $\lfloor\log(n+1)\rfloor-1$ 。
运用
合并
总的来说就是，对于当前两个左偏树 $A,B$ ，若有一个为空就返回另一个，否则令 $A$ 是键值小的，然后递归到 $A$ 的右儿子和 $B$ 的合并。最后往上更新距离。
单点插入
给新的值建个左偏树去合并。 $\mathcal{O}(\log n)$ 。
删顶
合并根左右子树。 $\mathcal{O}(\log n)$ 。
删已知结点
合并左右子树，往上更新距离。
建树
把每个结点作为左偏树放入一个队列。然后每次取出两个队首合并放进队尾，直到只有一个左偏树。 $\mathcal{O}(n)$ 。