看图说话之左式堆(优先队列)——原理解析及java实现
数据结构之左式堆(优先队列)——原理解析
一丶左式堆的基本概念
数据结构之二叉堆(优先队列)——原理解析文章中介绍了二叉堆的基本原理。本文介绍左式堆的基本原理，二叉堆是对优先队列的一种高效实现，左式堆是针对二叉堆合并操作困难的缺点，而提出的另外一种优先队列实现方式。
左式堆和二叉堆都具有一样的堆序性(大根堆和小根堆)，只是在结构性上有所不同，二叉堆是完全二叉树，左式堆不是完全二叉树其具有非常明显的不衡特征。为了介绍左式堆的结构性，必须介绍节点的npl(null paht length,零路径长度)属性。
图 1二叉树
节点的npl是指该节点到没有两个儿子的子节点(包括自身)的最短路径长。其中有几个特殊情况需要替注意：
（1）null节点的npl=-1
（2）叶子节点的npl=0。
（3）只有一个子节点的节点npl=0.
依据上述的npl定义和特殊情况，图1中二叉树各个节点的npl值如下图所示。
图2 二叉树的npl值
对于上图所示的根节点，其右节点没有两个儿子，所以依据定义，最短路径是到右节点的路径，路径长=1。通过图2所示的二叉树npl值分布，可以得到一个规律：任意节点的npl=Min(左节点npl，右节点npl)+1。
掌握了零路径长度的概念后，我们就可以介绍左式堆的结构性约束了，左式堆的结构性是指：对于任意节点，其左节点的npl>=右节点npl。这样的定义下左式堆的左子树深度会明显高与右子树，而且沿着右节点的右节点的路径走下去将是最短路径。如此定义一个树的结构有什么好处呢？
观察图1不难看出，图1代表的二叉树是一个二叉堆，观察图2和图1不难看出图1代表的二叉树不仅是二叉堆，而且还是左式堆。可见二叉堆是一种特殊的左式堆，左式堆在二叉堆的基础上调整了结构性，让其拥有较短的最右路径长度，用来高效的支持后续的合并操作。
二丶左式堆的合并操作
在了解了左式堆的基本概念后，我们知道左式堆是为了更有效的支持合并操作，而在二叉堆上作出的改进。本节通过图例的方式来讲解左式堆的合并过程。都是小根堆的前提下进行介绍。
图3 左式堆d1 图4 左式堆d2
1.比较d1和d2的根节点大小，将根节点较小的堆(d1)和根节点较大(d2)的堆的右子树进行合并，利用合并后的左式堆d3取代d1的右子树。
图4 堆合并中的拆分情况。
2.如图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;
}3.d2堆右子树和根节点较小的d1堆合并，重复步骤1合并结果如下。
此时发现了一个问题：合并后的结果不满足堆序的特点了，对于根节点18而言，其左节点15的npl=0，右节点10的npl=1.不满足左式堆对结构性的要求，所以此时需要左一个调整，将不满足堆序特定的节点18的左右子树互换。调整结果如下：
图6 堆序调整结果
通过图6所示的堆序调整步骤后，可以将这次合并的结果去替换d2堆的右子树了，替换结果如下图所示。
图7 d2堆右子树和d1堆合并结果替换d2堆右子树
这里也需要特别注意，在替换完成之后，需要检查根元素20是否满足堆序特性，观察图7所示的替换结果，根元素20满足堆序特点，无序调整堆序。 所以该次堆合并过程结束。
观察图7合并之后的结果，可发现合并之后依然是一个左式堆，其最右路径20-18-15依然是所有路径中最短的路径。
总结：
(1)在上述的堆合并过程中，我们可以清楚的看到堆合并的过程是递归的过程，在用代码实现堆合并过程时候，采用递归的程序设计可以更简单。
(2)在每次合并之后，需要检查根元素是否满足堆序特性，如果不满足需要调整堆序特性，调整堆序特性后需要更新npl值。
(3)从上述的结果中，合并堆的过程中，递归的次数取决于最右路径的长度，根据左式堆的结构性其最右路径最长为log(N)，一次合并操作的最坏时间复杂度是log(N)
三丶左式堆的插入操作
在知道左式堆合并的基础上，插入操作就很简单了。插入操作可以看成左式堆和只具有一个节点的左式堆的合并操作。那么其最坏时间复杂度也是log(N)。
四丶左式堆的删除操作
左式堆的删除操作在理解合并操作的基础上也十分简单，分为如下两个步骤：
1.返回根节点值
2.删除根节点，将左子树和右子树合并，合并后的结果就是删除操作后的新左式堆。
五丶左式堆的建堆过程
左式堆的建堆过程就是对输入元素重复插入过程，最坏时间复杂度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;
}
}
}