数据结构：左偏堆

左偏堆简介

又称左偏树、左倾堆，这么多名字都带个左，那就是因为它向左倾斜，和二叉堆一样都是一种优先队列实现方式。

左偏堆的一些定义

零距离（Null Path Length）：从一个节点到空节点的距离，简称NPL（这个理解看下图就立刻明白了）

image

左偏堆的性质

• [性质1] 节点的键值小于或等于它的左右子节点的键值。
• [性质2] 节点的左孩子的NPL >= 右孩子的NPL。
• [性质3] 节点的NPL = 它的右孩子的NPL + 1。

所有的操作就围绕着这三个性质，这是左偏树的所有操作的依据

合并

合并操作步骤

1. 如果两个空左倾堆合并，返回为空

2. 一个空左倾堆和非空左倾堆合并，返回非空左倾堆

3. 两个非空左倾堆合并

   第一步：比较两个堆的根节点，取较小根作为新的根节点，将较小堆的右孩子和较大的堆合并作为新根节点的右孩子

   第二部：如果新堆的右孩子的NPL>左孩子的NPL,交换左右孩子，更新新堆的根节点的NPL

图文讲解

合并是左偏树的精髓，插入，删除都要用到合并，这一节咱们用图来展示合并的过程

image

<center>比较两个堆的根元素大小（20，42），选择小的作为主堆</center>

image

<center>选择小堆的右子树（以72为根的子树）和以42为根的树进行比较</center>

image

<center>42<72,交换以42为根的树和以72为根的树的位置</center>

image

<center>继续选择右子树，重复上面的动作</center>

image

<center>比较86和72</center>

image

<center>交换位置</center>

image

<center>比较79和86</center>

image

<center>将86作为79的右子树</center>

image

<center>更新86的npl</center>

image

<center>继续更新，64的右子树的npl大于左子树的npl</center>

image

<center>更新npl,交换64的左右子树</center>

image

<center>更新npl,20的右子树npl大于左子树的npl</center>

image

<center>交换20的左右子树，20是整个堆的根节点到此结束</center>

合并代码实现

 public  Node merge(Node xHeap,Node yHeap){
        //任何一个堆为空，都将另一个堆作为主堆
        if(xHeap == null){
            return yHeap;
        }
        if(yHeap == null){
            return  xHeap;
        }
        //xheap作为主树，选择key小的作为主堆
        if(xHeap.getValue()>yHeap.getValue()){
            Node tem =xHeap;
            xHeap = yHeap;
            yHeap =tem;

        }
        //主堆的右子树是是主堆的右子树和yHeap合并的结果
        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;
        }
        //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;

    }

总结

左偏堆是可合并堆的一种堆，是实现优先队列的一种方式，左偏树的灵魂就是合并。如果不牵扯到合并，使用二叉堆就很方便，效率很高，如果会有合并的操作，左偏树是一种不错的选择。