看图说话之左式堆(优先队列)——原理解析及java实现

一丶左式堆的基本概念

数据结构之二叉堆(优先队列)——原理解析文章中介绍了二叉堆的基本原理。本文介绍左式堆的基本原理，二叉堆是对优先队列的一种高效实现，左式堆是针对二叉堆合并操作困难的缺点，而提出的另外一种优先队列实现方式。
左式堆和二叉堆都具有一样的堆序性(大根堆和小根堆)，只是在结构性上有所不同，二叉堆是完全二叉树，左式堆不是完全二叉树其具有非常明显的不衡特征。为了介绍左式堆的结构性，必须介绍节点的npl(null paht length,零路径长度)属性。

图 1二叉树

节点的npl是指该节点到没有两个儿子的子节点(包括自身)的最短路径长。其中有几个特殊情况需要替注意：

null节点的npl=-1
叶子节点的npl=0。
只有一个子节点的节点npl=0.

依据上述的npl定义和特殊情况，图1中二叉树各个节点的npl值如下图所示。

图2 二叉树的npl值

    对于上图所示的根节点，其右节点没有两个儿子，所以依据定义，最短路径是到右节点的路径，路径长=1。通过图2所示的二叉树npl值分布，可以得到一个规律：任意节点的npl=Min(左节点npl，右节点npl)+1。
    掌握了零路径长度的概念后，我们就可以介绍左式堆的结构性约束了，左式堆的结构性是指：对于任意节点，其左节点的npl>=右节点npl。这样的定义下左式堆的左子树深度会明显高与右子树，而且沿着右节点的右节点的路径走下去将是最短路径。如此定义一个树的结构有什么好处呢？
    观察图1不难看出，图1代表的二叉树是一个二叉堆，观察图2和图1不难看出图1代表的二叉树不仅是二叉堆，而且还是左式堆。可见二叉堆是一种特殊的左式堆，左式堆在二叉堆的基础上调整了结构性，让其拥有较短的最右路径长度，用来高效的支持后续的合并操作。

二丶左式堆的合并操作

在了解了左式堆的基本概念后，我们知道左式堆是为了更有效的支持合并操作，而在二叉堆上作出的改进。本节通过图例的方式来讲解左式堆的合并过程。都是小根堆的前提下进行介绍。

图3 左式堆d1和左式堆d2

比较d1和d2的根节点大小，将根节点较小的堆(d1)和根节点较大(d2)的堆的右子树进行合并，利用合并后的左式堆d3取代d1的右子树。

图4 堆合并中的拆分情况。
如图4所示，d2堆的右子树和d1堆合并后的左式堆充当d2的右子树则完成了合并操作，所以合并的问题转化成了d2堆右子树和d1堆合并的问题了。这明显是一个递归的过程,如下伪代码

publicLeftHeapNode merge(leftHeap d2,leftHeap d1){
   if(d2==null)return d2;
   d2.right = merge(d2.right,d2);
   return d2;
}

d2堆右子树和根节点较小的d1堆合并，重复步骤1合并结果如下。

图5 d1堆右子树和d1堆合并结果

此时发现了一个问题：合并后的结果不满足堆序的特点了，对于根节点18而言，其左节点15的npl=0，右节点10的npl=1.不满足左式堆对结构性的要求，所以此时需要左一个调整，将不满足堆序特定的节点18的左右子树互换。调整结果如下：

图6 堆序调整结果

    通过图6所示的堆序调整步骤后，可以将这次合并的结果去替换d2堆的右子树了，替换结果如下图所示。

图7 d2堆右子树和d1堆合并结果替换d2堆右子树

    这里也需要特别注意，在替换完成之后，需要检查根元素20是否满足堆序特性，观察图7所示的替换结果，根元素20满足堆序特点，无序调整堆序。所以该次堆合并过程结束。
    观察图7合并之后的结果，可发现合并之后依然是一个左式堆，其最右路径20-18-15依然是所有路径中最短的路径。

总结：

在上述的堆合并过程中，我们可以清楚的看到堆合并的过程是递归的过程，在用代码实现堆合并过程时候，采用递归的程序设计可以更简单。
在每次合并之后，需要检查根元素是否满足堆序特性，如果不满足需要调整堆序特性，调整堆序特性后需要更新npl值。
从上述的结果中，合并堆的过程中，递归的次数取决于最右路径的长度，根据左式堆的结构性其最右路径最长为log(N)，一次合并操作的最坏时间复杂度是log(N)

三丶左式堆的插入操作

在知道左式堆合并的基础上，插入操作就很简单了。插入操作可以看成左式堆和只具有一个节点的左式堆的合并操作。那么其最坏时间复杂度也是log(N)。

四丶左式堆的删除操作

左式堆的删除操作在理解合并操作的基础上也十分简单，分为如下两个步骤：

返回根节点值
删除根节点，将左子树和右子树合并，合并后的结果就是删除操作后的新左式堆。

五丶左式堆的建堆过程

左式堆的建堆过程就是对输入元素重复插入过程，最坏时间复杂度Nlog(N)，平均时间复杂度O(N)。

六丶左式堆的java代码实现。

二叉堆因为是完全二叉树的结构所以采用数组的存储结构，但是左式堆不是完全二叉树需采用链式的结构(需要支持合并操作，也需要采用链式存储结构)。

java代码的如下：

public classLeftHeap{
public HeapNode root;

public LeftHeap(int val){
   root= new HeapNode(val);
}

public void merge(LeftHeap heap){
   if(heap!=null){
       root=internalMerge(root,heap.root);
   }
}

private HeapNode internalMerge(HeapNode h1,HeapNode h2){
   if(h1==null) return h2;
   if(h2==null) return h1;
   HeapNode result =null;
   if(h1.val>=h2.val){
       h2.right = internalMerge(h2.right,h1);
       result =h2;
   }else{
       h1.right = internalMerge(h1.right,h2);
       result =h1;
   }
   //如果不满足结构性，则调整
   intleftNPL = result.left==null?-1:result.left.npl;
   intrightNPL = result.right==null?-1:result.right.npl;
   if(leftNPL<rightNPL){
       HeapNode temp = result.right;
       result.right = result.left;
       result.left = temp;
   }
   //更新npl值。
   result.npl = Math.min(leftNPL,rightNPL)+1;
   returnresult;
}
//对外暴露的插入函数
public void insert(int val){
   LeftHeap heap = new LeftHeap(val);
   merge(heap);
}
//对外暴露的删除函数
public int deleteMin(){
   if(root==null) return -1; //-1这里代表错误码，堆为空不删除。
   HeapNode node = root;
   root = internalMerge(root.left,root.right);
   returnnode.val;
}
public boolean isEmpty(){
   returnroot==null?true:false;
}

public static void main(String [] args){
   LeftHeap heap = new LeftHeap(2);
   for(int i=1;i<10;i++){
       heap.insert(i);
   }
   while(!heap.isEmpty()){
       System.out.print(heap.deleteMin()+" ");
   }
}
//左式堆的节点的定义
private static class HeapNode{
   publicint npl;
   publicHeapNode left;
   publicHeapNode right;
   publicint val;
   publicHeapNode(int val){
       this.val = val;
       left = null;
       left =null;
       npl =0;
   }
}

}
Reference:
[1] 数据结构与算法 java语言描述
[2] 博客原文