左偏树

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

不同于斜堆合并的,左偏堆的合并操作的为 ，而完全二叉堆为 ，所以左偏堆适合基于合并操作的情形。

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

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

当且仅当节点 i 的左子树或右子树为空时，节点被称作外节点（实际上保存在二叉树中的节点都是内节点，外节点是逻辑上存在而无需保存。把一颗二叉树补上全部的外节点，则称为extended binary tree）。节点i的距离是节点 i 到它的后代中的最近的外节点所经过的边数。特别的，如果节点 i 本身是外节点，则它的距离为0;而空节点的距离规定为 -1。《左偏树的特点及其应用》黄源河2005全国青少年信息学奥林匹克竞赛冬令营国家集训队论文

 性质 
 节点的键值小于或等于它的左右子节点的键值。
 节点的左子节点的距离不小于右子节点的距离。
 节点的距离等于它的右子节点的距离加1。
 一棵N个节点的左偏树root节点的距离最多为log(N+1)-1。
 操作

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

第一种是每次选择一个节点与树合并，直到所有节点都合并为一个树。这种方法不太有效，时间复杂度为。

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

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

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

Java代码实现合并两棵左偏的最小树：
 root键值最小的树的右子树与其它树合并；
 上步合并结果作为与root键值最小树的右子树。
 比较root的左右子树的距离值（s-value），如果右子树大于左子树则交换两棵子树
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;
}

其他操作
增加一个节点、删除根节点、初始化一批数据，都是基于合并操作。

参考文献

延伸阅读
Leftist Trees , Sartaj Sahni
傅清祥,王晓东 算法与数据结构(第二版) 电子工业出版社
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms (Second Edition) The MIT Press
Mark Allen Weiss Data Structures and Algorithm Analysis in C (Second Edition) Pearson Education

Category:堆
Category:算法
Category:树结构