查看“︁左偏树”︁的源代码

{{NoteTA
|G1 = IT
}}
'''左偏树'''（{{lang-en|Leftist tree}}），也可称为'''左偏堆'''、'''左倾堆'''，是[[计算机科学]]中的一种[[树 (数据结构)|树]]，是一种[[优先队列]]实现方式，属于[[可并堆|可并]][[堆 (数据结构)|堆]]，在[[信息学]]中十分常见，在统计问题、最值问题、模拟问题和[[贪心法|贪心问题]]等等类型的题目中，左偏树都有着广泛的应用。[[斜堆]]是比左偏树更为一般的数据结构。

不同于[[斜堆]]合并的{{Tsl|en|average-case complexity|平均情況複雜度}},左偏堆的合并操作的{{Tsl|en|Worst-case complexity|最壞情況複雜度}}为 <math>O(log n)</math>，而完全二叉堆为 <math>O(n)</math>，所以左偏堆适合基于合并操作的情形。

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

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

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

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

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

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

第二种方法是使用[[队列]]，将队列中前两个节点合并，将合并后的新节点放到队列的末尾，直到队列中只有一个节点。这种方法的时间复杂度为<math>O(n)</math>。

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

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

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

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

==参考文献==
<references/>

==延伸阅读==
*[http://www.cise.ufl.edu/~sahni/cop5536/powerpoint/lec11.ppt Leftist Trees] {{Wayback|url=http://www.cise.ufl.edu/~sahni/cop5536/powerpoint/lec11.ppt |date=20170215102502 }}, [[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

{{Data structures}}
{{计算机科学中的树}}

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