Introduction to left offset heap

Also known as left-leaning tree, left-leaning heap, so many names with a left, that is because it leans to the left, like a binary heap is a priority queue implementation.

Some definitions of left-biased heap

Null Path Length: The distance from a node to an empty node (NPL).

Properties of left biased heaps

  • Property 1 the key value of a node is less than or equal to the key value of its left and right children.
  • [Property 2] NPL of the left child of the node >= NPL of the right child.
  • Property 3: NPL of a node = NPL + 1 of its right child.

All of the operations revolve around these three properties, which are the basis of all operations on left-biased trees

merge

Merge operation Procedure

  1. If two empty left-leaning heaps merge, return empty

  2. An empty left heap is merged with a non-empty left heap to return the non-empty left heap

  3. Two non-empty left-leaning heaps merge

    Step 1: Compare the root nodes of the two heaps, take the smaller root as the new root node, and merge the right child of the smaller heap and the larger heap as the right child of the new root node

    Step 2: If the NPL of the right child of the new heap > the NPL of the left child, swap the left child and update the NPL of the root node of the new heap

Graphic interpretation of the

Merge is the essence of a left-sided tree, and it’s used for both insertion and deletion, so in this video we’re going to use a diagram to illustrate the merge process

Merge code implementation

 public  Node merge(Node xHeap,Node yHeap){
        // If any heap is empty, make the other heap the main heap
        if(xHeap == null) {return yHeap;
        }
        if(yHeap == null) {return  xHeap;
        }
        // The xheap is the primary tree, and the one with the smallest key is the primary heap
        if(xHeap.getValue()>yHeap.getValue()){
            Node tem =xHeap;
            xHeap = yHeap;
            yHeap =tem;

        }
        // The right subtree of the main heap is the result of the combination of the right subtree of the main heap and the 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(a){
        if(left ==null||right ==null){
            npl = 0;
        }
        npl = right.getNpl()+1;

  }
Copy the code

delete

In this case, deletion refers to the removal of the minimum (maximum), which is the root node. We simply merge the left and right nodes of the root node

 // delete the minimum value, which is the root node
    public  boolean  remove(a){
        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;

    }    
Copy the code

insert

An insert can be viewed as a left biased tree with only one node merging with another tree

 public  void inserNode(int key){
       Node node = createNode(key);
       root = merge(root,node);
   }
Copy the code

An extension extension – inclined pile

Inclined heap is a variant of left-biased tree. The difference is that the inclined heap does not have the concept of zero distance. After merging, it does not need to judge the NPL, but directly exchange the left and right children, which is to remove the NPL judgment. Personally, inclined heap and left biased heap are the same thing, but there are some differences in the strategy of maintaining relative balance, there is no substantial difference.

 public  Node merge(Node xHeap,Node yHeap){
        if(xHeap == null) {return yHeap;
        }
        if(yHeap == null) {return  xHeap;
        }
        // Xheap is the primary tree
        if(xHeap.getValue()>yHeap.getValue()){
            Node tem =xHeap;
            xHeap = yHeap;
            yHeap =tem;

        }
        xHeap.setRight(merge(xHeap.getRight(),yHeap));
        if(xHeap.getLeft()==null) {// The difference is in this line
            Node left = xHeap.getLeft();
            Node right =xHeap.getRight();
            xHeap.setRight(left);
            xHeap.setLeft(right);
        }
        xHeap.updateNpl();
        return xHeap;

    }
Copy the code

conclusion

Left-biased heap is a kind of heap of mergable heap, which is a way to realize priority queue. The soul of left-biased tree is merge. If there is no merge involved, it is very convenient and efficient to use binary heaps, and if there is a merge operation, left-biased trees are a good choice.