欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-06 20:55:47
...

 数据结构之左式堆(优先队列)——原理解析

一丶左式堆的基本概念

   数据结构之二叉堆(优先队列)——原理解析文章中介绍了二叉堆的基本原理。本文介绍左式堆的基本原理,二叉堆是对优先队列的一种高效实现,左式堆是针对二叉堆合并操作困难的缺点,而提出的另外一种优先队列实现方式。

左式堆和二叉堆都具有一样的堆序性(大根堆和小根堆),只是在结构性上有所不同,二叉堆是完全二叉树,左式堆不是完全二叉树其具有非常明显的不衡特征。为了介绍左式堆的结构性,必须介绍节点的npl(null paht length,零路径长度)属性。

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

              图 1二叉树

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

(1)null节点的npl=-1

(2)叶子节点的npl=0。

(3)只有一个子节点的节点npl=0.

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

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

         图2 二叉树的npl值

      对于上图所示的根节点,其右节点没有两个儿子,所以依据定义,最短路径是到右节点的路径,路径长=1。通过图2所示的二叉树npl值分布,可以得到一个规律:任意节点的npl=Min(左节点npl,右节点npl)+1。

      掌握了零路径长度的概念后,我们就可以介绍左式堆的结构性约束了,左式堆的结构性是指:对于任意节点,其左节点的npl>=右节点npl。这样的定义下左式堆的左子树深度会明显高与右子树,而且沿着右节点的右节点的路径走下去将是最短路径。如此定义一个树的结构有什么好处呢?

      观察图1不难看出,图1代表的二叉树是一个二叉堆,观察图2和图1不难看出图1代表的二叉树不仅是二叉堆,而且还是左式堆。可见二叉堆是一种特殊的左式堆,左式堆在二叉堆的基础上调整了结构性,让其拥有较短的最右路径长度,用来高效的支持后续的合并操作。

二丶左式堆的合并操作

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

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

           图3 左式堆d1                                                                                图4 左式堆d2

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

 

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

             图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合并结果如下。

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

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

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

   

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

             图6 堆序调整结果

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

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

    图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;
       }
    }
}