LeftistHeap - Implementation in Java

Leftist (min)Heap  

Definition:

A Leftist (min)Heap is a binary tree that satisfies the follow-ing conditions.  If X is a node and L and R are its left and right children, then:
 X.value <= L.value
 X.value <= R.value
 null path length of L >=  null path length of R
where the null path length of a node is the shortest distance between from that node to a descendant with 0 or 1 child.
If a node is null, its null path length is  -1.

 Example : Null Path Length

 Merging Leftist Heaps

 





 

 





 


 

Final Leftist Heap

 

Algorithm Merge

Implementation

/* Program Name: LeftistHeap.java
 * Author: Sarju
 * eMail: sarjusjcet@gmail.com,sarju@csesjcet.org
 * Date: 16-10-12
 * *
 */
 import java.io.*;
class node{
    int data;
    node left, right;
    int npl;
    }

class minLeftist{
    node root = null;
    public void insert(){
        int newElement;
        try{
        /*Creating New Node*/
        System.out.println("Enter the new element to insert:");
        DataInputStream din  = new DataInputStream(System.in);
        newElement = Integer.parseInt(din.readLine());
        node temp = new node();
        temp.data = newElement;
        temp.left=temp.right=null;
        temp.npl = 0;
        if(root==null)//Tree Empty
            root=temp;
        else
            root = merge(root,temp);
            }
        catch(Exception e){}
    }
    /*Function for Calculating the null path length*/
    int dis(node a){
    if(a==null)
        return -1;
        else
        return a.npl;
    }
    /*Function for merging two Leftist Heaps*/
    public node merge(node a, node b){
        if (a==null) return b;
        if (b==null) return a;
        if(b.data            /*Swap(a,b)*/
            node temp;
            temp=a;
            a=b;
            b=temp;
            root=a;
            }
        a.right = merge(a.right,b);
        /*Cheking for the Leftist Property Violation*/
        if(dis(a.right)>dis(a.left)){
            //swap(a.right,a.left);
            node temp;
            temp=a.right;
            a.right=a.left;
            a.left=temp;
            }
        /*Calculating the null path length*/
        if(a.right == null)
            a.npl = 0;
        else{
            a.npl = 1+ a.right.npl;
            }
        return a;
        }
    /*Function for deleting minimum element from the Leftist Heap*/
    public void delMin(){
    System.out.println("Deleted Element Is:"+root.data);
    root = merge(root.left,root.right);
    }
    /*Display Heap Using Inorder Traversal*/
    public void display(){
        if(root==null)
            System.out.println("Leftist Heap Empty");
        else
            inorder(root);
    }
    public void inorder(node cur_node){
    if(cur_node!=null){
        inorder(cur_node.left);
        System.out.println(cur_node.data+"("+cur_node.npl+")");
        inorder(cur_node.right);
    }  
    }
}
/*Main Class*/
class LeftistHeap{
public static void main(String[] argv) {
    int choice,element;
    minLeftist m = new minLeftist();
    try{
        do{  
      
        System.out.print("\n1:Insert\n2.DeleteMin\n3.Exit");
        System.out.print("\nEnter Your Choice:");
        DataInputStream din  = new DataInputStream(System.in);
        choice = Integer.parseInt(din.readLine());
        switch(choice){
            case 1: /*For Adding new Element*/
                    m.insert();
                    m.display();
                    break;
            case 2:
                    /*Deleting Min Element*/
                    m.delMin();
                    m.display();
                    break;          
        }
        }while(choice<3 br="br">        }
        catch(Exception e){
        }
}
}