又称左偏树、左倾堆，这么多名字都带个左，那就是因为它向左倾斜，和二叉堆一样都是一种优先队列实现方式。
左偏堆的一些定义
零距离（Null Path Length）：从一个节点到空节点的距离，简称NPL（这个理解看下图就立刻明白了）
左偏堆的性质
[性质1] 节点的键值小于或等于它的左右子节点的键值。
[性质2] 节点的左孩子的NPL >= 右孩子的NPL。
[性质3] 节点的NPL = 它的右孩子的NPL + 1。
所有的操作就围绕着这三个性质，这是左偏树的所有操作的依据
合并操作步骤
如果两个空左倾堆合并，返回为空
一个空左倾堆和非空左倾堆合并，返回非空左倾堆
两个非空左倾堆合并
第一步：比较两个堆的根节点，取较小根作为新的根节点，将较小堆的右孩子和较大的堆合并作为新根节点的右孩子
第二部：如果新堆的右孩子的NPL>左孩子的NPL,交换左右孩子，更新新堆的根节点的NPL
合并是左偏树的精髓，插入，删除都要用到合并，这一节咱们用图来展示合并的过程
比较两个堆的根元素大小（20，42），选择小的作为主堆
选择小堆的右子树（以72为根的子树）和以42为根的树进行比较
42<72,交换以42为根的树和以72为根的树的位置
继续选择右子树，重复上面的动作
比较86和72
比较79和86
将86作为79的右子树
更新86的npl
继续更新，64的右子树的npl大于左子树的npl
更新npl,交换64的左右子树
更新npl,20的右子树npl大于左子树的npl
交换20的左右子树，20是整个堆的根节点到此结束
合并代码实现
public Node merge(Node xHeap,Node yHeap){
if(xHeap == null){
return yHeap;
if(yHeap == null){
return xHeap;
if(xHeap.getValue()>yHeap.getValue()){
Node tem =xHeap;
xHeap = yHeap;
yHeap =tem;
xHeap.setRight(merge(xHeap.getRight(),yHeap));
if(xHeap.getLeft()==null||xHeap.getLeft().getNpl()<xHeap.getRight().getNpl()) {
Node left = xHeap.getLeft();
Node right =xHeap.getRight();
xHeap.setRight(left);
xHeap.setLeft(right);
xHeap.updateNpl();
return xHeap;
public void updateNpl(){
if(left ==null||right ==null){
npl = 0;
npl = right.getNpl()+1;
这里的删除是指的是删除最小值（最大值），也就是根节点。我们只需将根节点的左右节点合并就可以了
public boolean remove(){
if(root == null){
return false;
if(root.getLeft()!=null){
root.getLeft().setParent(null);
if(root.getRight()!=null){
root.getRight().setParent(null);
root= merge(root.getLeft(),root.getRight());
return true;
插入操作可以看做一个只有一个节点的左偏树和另一棵树合并
public void inserNode(int key){
Node node = createNode(key);
root = merge(root,node);
一个拓展延伸 —— 斜堆
斜堆是左偏树的一个变种，差异就是斜堆没有零距离的概念，合并后不用判断NPL，直接交换左右孩子，也就是去掉NPL判断。个人感觉斜堆和左偏堆是一个东西，只是在保持相对平衡上的策略有所差异，没什么实质的区别。
public Node merge(Node xHeap,Node yHeap){
if(xHeap == null){
return yHeap;
if(yHeap == null){
return xHeap;
if(xHeap.getValue()>yHeap.getValue()){
Node tem =xHeap;
xHeap = yHeap;
yHeap =tem;
xHeap.setRight(merge(xHeap.getRight(),yHeap));
if(xHeap.getLeft()==null) {
Node left = xHeap.getLeft();
Node right =xHeap.getRight();
xHeap.setRight(left);
xHeap.setLeft(right);
xHeap.updateNpl();
return xHeap;
左偏堆是可合并堆的一种堆，是实现优先队列的一种方式，左偏树的灵魂就是合并。如果不牵扯到合并，使用二叉堆就很方便，效率很高，如果会有合并的操作，左偏树是一种不错的选择。
