由于左偏堆已经不是左偏树完全二叉树，左偏树都有着广泛的左偏树应用。

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