优先队列之左式堆

什么叫做左式堆呢？他就是跟二叉堆一样具有结构性和有序性，也就是说它是基于二叉堆的一个提升，他们的唯一区别就是左式堆是非常不平衡的。左式堆是一个有效支持合并操作的数据结构。

关于二叉堆可以看我之前写的博文

左式堆的性质

首先我们要知道，左式堆有一个npl值null path length，也就是任意节点到一个没有两个孩子节点的最短路径。

而他的性质则是对于任意一个节点左子树的npl值至少等于右子树的npl值。也就是说左孩子的npl大于等于右孩子的npl值。

节点具有一个孩子节点或者没有孩子的节点的npl值为0。且npl（null）=-1.

左式堆左式堆顾名思义我们要保证根节点的左子树长度大于右子树！！

如图

在这个图片当中左边的是左式堆，右边的不是

左边的为什么是呢？我们看1这个根节点，左孩子2的npl为1，右孩子的为0，左大于右成立，再往下走2，他的左孩子没有孩子所以npl=0，而他的右孩子5有一个孩子所以npl也等于0成立，所以对于任意一个节点他的左孩子的npl大于等于右孩子的npl成立，所以为左式堆。

再者我们看右边这个，1那个根节点都是一样的，所以我们直接看2这个节点，他的左孩子的没有孩子节点所以npl=0，而右孩子5有两个孩子节点所以5这个节点的npl=1.即右孩子的npl大于左孩子的npl不符合左式堆的性质，所以不是。

算法实现

因为左式堆的基本操作是合并，所以我们可以把插入看作为合并的一种特殊情形。

接下来我们看具体实现，首先我们要创建一个内部类当作节点，他又左孩子有孩子还有npl。

public class MyLeftHeap
   
    > {
       private class HeapNode
    
     {
           AnyType data;        HeapNode
     
       left;        HeapNode
      
        right;        int npl;      //npl 是节点到下一个不具有两孩子节点的最短路径长        public HeapNode(AnyType data){
   this(data,null,null);}        public HeapNode(AnyType data,HeapNode
       
         left,HeapNode
        
          right){ this.data=data; this.left=left; this.right=right; npl=0; } }

接着我们进行初始化操作，也就是产生一个根节点但是没插入之前他是空的。

private HeapNode
   
     root;    public MyLeftHeap(){
   root=null;}    public boolean isEmpty(){
   return root==null;}    public void makeEmpty(){
   root=null;}

合并

接下来的就是合并，我们把一个新的左式堆放入，如果这俩是一个堆则不操作。我们把加入合并的那个堆的根与我们原本的堆的根进行合并判断，并返回给我们原本的根。

//merge 合并    public void merge(MyLeftHeap
   
     heap){
           if(this==heap)            return;        root=merge(root,heap.root);        heap.root=null;    }

根据输入的节点信息，判断是否哪个节点为空，一个空则返回另一个节点。若都不为空，则比较两个节点的数据谁大，把大的放在小的右子树空的位置。

private HeapNode
   
     merge(HeapNode
    
      node1,HeapNode
     
       node2){
           if(node1==null)            return node2;        if(node2==null)            return node1;        if(node1.data.compareTo(node2.data)<0)            return merge_operate(node1,node2);        else            return merge_operate(node2,node1);    }

判断他是不是一个没有孩子的节点，没有孩子则放到左子树上，否则把右子树和要合并的堆进行递归操作直到把合并的树放上去。如果右子树的nol大于左子树了，则交换左右子树位置达到要求。

private HeapNode
   
     merge_operate(HeapNode
    
      n1,HeapNode
     
       n2){
           if(n1.left==null)            n1.left=n2;        else {
               n1.right=merge(n1.right,n2);            if(n1.left.npl
      
        node){
           HeapNode
       
         temp=node.right;        node.right=node.left;        node.left=temp;    }

之前我们说过插入是一种特殊的合并，那么删除最小的何尝又不是呢？插入的时候我们把一个新的节点归并到原本的堆当中，而删除最小的也就是当我们把根节点去掉之后，我们把他左右孩子节点进行归并不就是又得到了一个新的左式堆？

//insert    public void insert(AnyType data){
   root=merge(new HeapNode<>(data),root);}    //deleteMin    public AnyType deleteMin(){
           AnyType min=root.data;        root=merge(root.left,root.right);        return min;    }}

测试

public class test {
       public static void main(String[] args) {
          MyLeftHeap
   
     a=new MyLeftHeap<>();       a.insert(1);       a.insert(2);       a.insert(3);       a.insert(4);        MyLeftHeap
    
      b=new MyLeftHeap<>();        b.insert(11);        b.insert(21);        b.insert(31);        b.insert(41);        a.merge(b);        while (!a.isEmpty())            System.out.println(a.deleteMin());    }}

结果

在这里插入图片描述

转载地址：http://grqai.baihongyu.com/

你可能感兴趣的文章