左偏树

维基百科,自由的百科全书
跳转至: 导航搜索

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

左偏堆的合并操作的平摊时间复杂度为O(log n),而完全二叉堆为O(n)。左偏堆适合基于合并操作的情形。

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

定义[编辑]

左偏树的节点的距离值

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

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

性质[编辑]

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

操作[编辑]

合并两颗左偏树[编辑]

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

  1. root键值最小的树的右子树与其它树合并;
  2. 上步合并结果作为与root键值最小树的右子树。
  3. 比较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;
}

其他操作[编辑]

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

参考文献[编辑]

  1. ^ 《左偏树的特点及其应用》 黄源河 2005全国青少年信息学奥林匹克竞赛冬令营国家集训队论文

延伸阅读[编辑]

  • 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