左偏树

左偏树（英语：leftist tree或leftist heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。

不同于斜堆合并的平均情况复杂度（英语：average-case complexity）,左偏堆的合并操作的最坏情况复杂度（英语：Worst-case complexity）为O(log n)，而完全二叉堆为O(n)，所以左偏堆适合基于合并操作的情形。

由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。

左偏树是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针（left, right）外，还有两个属性：键值和距离（英文文献中称为s-value）。键值用于比较节点的大小。距离的定义如下：

当且仅当节点 i 的左子树或右子树为空时，节点被称作外节点（实际上保存在二叉树中的节点都是内节点，外节点是逻辑上存在而无需保存。把一颗二叉树补上全部的外节点，则称为extended binary tree）。节点i的距离是节点 i 到它的后代中的最近的外节点所经过的边数。特别的，如果节点 i 本身是外节点，则它的距离为0;而空节点的距离规定为 -1。

初始化左偏树有两种方式。

第一种是每次选择一个节点与树合并，直到所有节点都合并为一个树。这种方法不太有效，时间复杂度为${\displaystyle O(nlogn)}$。

第二种方法是使用队列，将队列中前两个节点合并，将合并后的新节点放到队列的末尾，直到队列中只有一个节点。这种方法的时间复杂度为${\displaystyle O(n)}$。

假设堆是小根堆，合并时选择关键字较小的节点作为根节点，然后将关键字大的节点与根节点的右子堆合并。

在合并之后，比较子堆的s值。通过交换左右子堆来保证左节点的s值始终大于等于右节点。然后更新节点的s值。

Java代码实现合并两棵左偏的最小树：

public Node merge(Node x, Node y) {  if(x == null)    return y;  if(y == null)     return x;  // if this was a max height biased leftist tree, then the   // next line would be: if(x.element < y.element)  if(x.element.compareTo(y.element) > 0) {      // x.element > y.element    Node temp = x;    x = y;    y = temp;  }  x.rightChild = merge(x.rightChild, y);  if(x.leftChild == null) {    // left child doesn't exist, so move right child to the left side    x.leftChild = x.rightChild;    x.rightChild = null;  } else {    // left child does exist, so compare s-values    if(x.leftChild.s < x.rightChild.s) {      Node temp = x.leftChild;      x.leftChild = x.rightChild;      x.rightChild = temp;    }    // since we know the right child has the lower s-value, we can just    // add one to its s-value    x.s = x.rightChild.s + 1;  }  return x;}