[科普中国]-左偏树

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

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

不同于斜堆合并的平均情况复杂度,左偏堆的合并操作的最坏情况复杂度为O(log n)，而完全二叉堆为O(n)，所以左偏堆适合基于合并操作的情形。

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

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

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

性质节点的键值小于或等于它的左右子节点的键值。1

节点的左子节点的距离不小于右子节点的距离。

节点的距离等于它的右子节点的距离加1。

一棵N个节点的左偏树root节点的距离最多为log(N+1)-1。

操作合并两颗左偏树Java代码实现合并两棵左偏的最小树：

root键值最小的树的右子树与其它树合并；

上步合并结果作为与root键值最小树的右子树。

比较root的左右子树的距离值（s-value），如果右子树大于左子树则交换两棵子树

publicNodemerge(Nodex,Nodey){if(x==null)returny;if(y==null)returnx;//ifthiswasamaxheightbiasedleftisttree,thenthe//nextlinewouldbe:if(x.element0){//x.element>y.elementNodetemp=x;x=y;y=temp;}x.rightChild=merge(x.rightChild,y);if(x.leftChild==null){//leftchilddoesn'texist,somoverightchildtotheleftsidex.leftChild=x.rightChild;x.rightChild=null;}else{//leftchilddoesexist,socompares-valuesif(x.leftChild.s