左倾堆
堆(heap)被为优先队列(priority queue)，但并不是队列按先后顺序来取出元素，而是按照元素的优先级。上一节的 索引堆、二叉堆 也是。
这一节我们来介绍左倾堆
左倾堆的介绍
左偏树（英语：leftist tree或leftist heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式 ━━＞ 维基百科
当优先队列需要解决“两个优先队列合并”的问题时，二叉堆的效率就比较差了，这时左倾堆等方式可以很好的解决这类问题。左倾堆合并时间复杂度为O(lgn)。左倾堆在统计问题，最值问题，模拟问题和贪心问题等问题中有广泛的应用。 左倾堆是二叉树，另外还有两个属性，键值和零距离。 ━━＞ 来自这里
不同于斜堆合并的平均情况复杂度,左偏堆的合并操作的最坏情况复杂度为O(log n)，而完全二叉堆为O(n)，所以左偏堆适合基于合并操作的情形。
由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。
- 左子树
- 右子树
- 键值
- NPL
键值
用来比较节点的大小
零距离( NPL )
是 null path length 的缩写，指的是从该结点到达一个没有两个孩子的结点（一个或无孩子）的最短距离，叶节点的NPL为0, NULL的NPL为-1。
左倾堆的性质
- 节点的优先级大于或等于它子节点的优先级
- 任意节点左孩子的NPL >= 右孩子的NPL
- 节点的NPL = 它的右孩子的NPL + 1
下图是 NPL 的示意图：
合并操作图解
合并操作是左倾堆的重点。合并两个左倾堆的过程如下：
- 如果一个空左倾堆与非空左倾堆合并，返回非空左倾堆;
- 如果两个左倾堆都非空，比较两个根节点，取优先级高的根节点为新的根节点。将“优先级较高堆的根节点的右孩子”和“优先级底的堆”进行合并;
- 如果新堆的右孩子的NPL > 左孩子的NPL，则交换左右孩子;
- 设置新堆的根节点的NPL = 右子堆NPL + 1;
下图将是我们合并的两个左倾堆：
第一步 将
较小堆(根为10)的右孩子和较大堆(根为12)进行合并
因为 根为 10 的堆 比 根为 12 的堆 优先级高，根为 10 的根节点 作为新节点
第二步 将上一步得到的
根 12 的右子树和根为 15 的树进行合并第三步 将上一步得到的
根 15 的右子树和根为 22 的树进行合并
第四步 将上一步得到的
根 22 的右子树和根为 27 的树进行合并
至此，已经成功的将两棵树合并成为一棵树了。接下来，对新生成的树进行调节。
第五步 上一步得到的
树22的右孩子的NPL > 左孩子的NPL，因此交换左右孩子
第六步 上一步得到的
树13的右孩子的NPL > 左孩子的NPL，因此交换左右孩子
第七步 上一步得到的
树10的右孩子的NPL > 左孩子的NPL，因此交换左右孩子
至此，合并完毕。上面就是合并得到的左倾堆！
最后，Demo 在这里