简介
左偏树是一种树形数据结构，更准确地说，是一种堆形数据结构，因此又叫左偏堆（左堆）。
什么叫“堆形”？简单来讲，就是满足如下性质的一种数据结构。
堆性：一个树形数据结构，满足其子节点和父节点的键值具有某种关系这一性质。
常见的堆有大根堆、小根堆等，这名字也非常形象——可以想象一个类似汉诺塔的堆状物，或是一些集装箱叠起来的东西，一般人们都习惯把大箱子放在小箱子上面“堆”起来。
左偏树是一种特殊的堆，它在堆的基础上多了“左偏性”，这正是它保证合并复杂度的关键所在。而斜堆是左偏堆的一个变种，它省掉了左偏堆的“交换左右子树”的操作，并且在均摊意义下仍能保证复杂度正确。
下面文章主要讲左偏堆，斜堆将在最后部分作为拓展引出。
性质
在提到左偏性之前，需要引入两个重要的概念：外节点和距离。
外节点：左偏树中儿子数小于2的节点。
距离：对于左偏树上一个点，它的距离定义为到离他最近的外节点所要经过的边数。特别地，外节点距离为0，空节点距离为-1。
基于此引入左偏树的基本性质。
左偏性：对于左偏树上任何一个点，$dis_{leftson} \ge dis_{rightson}$。
上图是个左偏树的实例，图中黑色表示键值，红色表示距离，以大根堆为例。
按照这个基本性质，我们很容易得到一些推论。
推论1：$dis_{node}=dis_{rightson} + 1$
这是因为右儿子距离总是较小的，按“最近”这个定义可以很容易看出来。
推论2：$dis_{node} \le \log_{2} (N+1)-1$
其中N是节点总数，并且当且仅当其为完全二叉树时，并且node为根节点时取等。
我们可以只考虑根节点，因为如果存在子节点的距离更大，我们可以递归地考虑那个子树，显然此时 N 更小，不等式更强了。
而假设根节点的距离为d，也即一直往根节点右手走有d这么长，那么点最少的情况一定是完全二叉树，此时点数为
因此得证。
时间复杂度
由于左偏树主要优势在于合并，而添加节点、删除节点都可以通过合并来达到（事实上，可并堆的插入、删除都可以这样归结为合并），因此这里只考虑合并这一操作。
左偏堆的合并操作：
- 记根较小的树为 u，则递归合并：
merge(u, v) = merge(v, u \rightarrow rightSon)。 - 递归终止：当待合并两树中有一者为空时，直接返回非空。
- 合并后：更新左右子树的 $dis$，如果违反了左偏性，交换左右子树。
由于每次合并都取一个树的右子树，由推论 2 知道每次会使一个树根的距离值减1，因此递归深度的级别为 $\log\ n$。
因此合并操作的时间复杂度级别为 $O(\log\ n)$。
斜堆
待更新，需要使用势能摊还法证明，作者需要学习一下…