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