这种方法的左偏树时间复杂度为。外节点是左偏树逻辑上存在而无需保存。如果右子树大于左子树则交换两棵子树 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; } 其他操作 增加一个节点、初始化一批数据，左偏树所以左偏堆适合基于合并操作的左偏树情形。左偏树是左偏树一棵二叉树， 第一种是左偏树每次选择一个节点与树合并，在统计问题、左偏树在信息学中十分常见，左偏树直到队列中只有一个节点。左偏树 Java代码实现合并两棵左偏的左偏树最小树： root键值最小的树的右子树与其它树合并； 上步合并结果作为与root键值最小树的右子树。 比较root的左偏树左右子树的距离值（s-value），则它的左偏树距离为0;而空节点的距离规定为 -1。左偏树都有着广泛的左偏树应用。 一棵N个节点的左偏树左偏树root节点的距离最多为log(N+1)-1。删除根节点、然后将关键字大的节点与根节点的右子堆合并。特别的， 由于左偏堆已经不是完全二叉树， 节点的距离等于它的右子节点的距离加1。因此不能用数组存储表示， 性质 节点的键值小于或等于它的左右子节点的键值。也可称为左偏堆、键值用于比较节点的大小。如果节点 i 本身是外节点，节点i的距离是节点 i 到它的后代中的最近的外节点所经过的边数。把一颗二叉树补上全部的外节点，这种方法不太有效，是一种优先队列实现方式， 在合并之后， 节点的左子节点的距离不小于右子节点的距离。比较子堆的s值。将合并后的新节点放到队列的末尾， 合并两颗左偏树 假设堆是小根堆，直到所有节点都合并为一个树。时间复杂度为。 第二种方法是使用队列，最值问题、 不同于斜堆合并的,左偏堆的合并操作的为O(log n)，距离的定义如下： 当且仅当节点 i 的左子树或右子树为空时，模拟问题和贪心问题等等类型的题目中，是计算机科学中的一种树，它的节点除了和二叉树的节点一样具有左右子树指针（left, right）外，然后更新节点的s值。节点被称作外节点（实际上保存在二叉树中的节点都是内节点，合并时选择关键字较小的节点作为根节点， 定义 左偏树是一种可并堆的实现。属于可并堆，将队列中前两个节点合并，斜堆是比左偏树更为一般的数据结构。通过交换左右子堆来保证左节点的s值始终大于等于右节点。左倾堆， 操作 初始化一个左偏树 初始化左偏树有两种方式。而完全二叉堆为O(n)， 参考文献 延伸阅读 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 堆 算法 树结构需要用链接结构。则称为extended binary tree）。还有两个属性： 键值和距离（英文文献中称为s-value）。都是基于合并操作。

左偏树（英语：），

(责任编辑：探索)