Java Program to Implement Leftist Heap

This is a Java Program to implement Leftist Heap. A leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value.

Here is the source code of the Java program to implement Leftist Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 *  Java Program to Implement LeftistHeap
 **/
 
import java.util.Scanner;
 
/** Class LeftHeapNode **/    
class LeftHeapNode
{
    int element, sValue;     
    LeftHeapNode left, right;             
 
    public LeftHeapNode(int ele)
    {
        this(ele, null, null);
    }
    public LeftHeapNode(int ele, LeftHeapNode left, LeftHeapNode right)
    {
        this.element = ele;
        this.left = left;
        this.right = right;
        this.sValue = 0;
    }    
}
 
/** Class LeftistHeap **/
class LeftistHeap
{
    private LeftHeapNode root; 
 
    /** Constructor **/
    public LeftistHeap() 
    {
        root = null;
    }
 
    /** Check if heap is empty **/
    public boolean isEmpty() 
    {
        return root == null;
    }
 
    /** Make heap empty **/ 
    public void clear( )
    {
        root = null;
    }
 
    /** Function to insert data **/
    public void insert(int x )
    {
        root = merge(new LeftHeapNode( x ), root);
    }
 
    /** Function merge **/
    public void merge(LeftistHeap rhs)
    {
        if (this == rhs)    
            return;
        root = merge(root, rhs.root);
        rhs.root = null;
    }
 
    /** Function merge **/
    private LeftHeapNode merge(LeftHeapNode x, LeftHeapNode y)
    {
        if (x == null)
            return y;
        if (y == null)
            return x;
        if (x.element > y.element)
        {
            LeftHeapNode temp = x;
            x = y;
            y = temp;
        }
 
        x.right = merge(x.right, y);
 
          if(x.left == null) 
          {
            x.left = x.right;
            x.right = null;         
        } 
        else 
        {
            if(x.left.sValue < x.right.sValue) 
            {
                LeftHeapNode temp = x.left;
                  x.left = x.right;
                  x.right = temp;
            }
            x.sValue = x.right.sValue + 1;
        }        
        return x;
    }
 
    /** Function to delete minimum element **/
    public int deleteMin( )
    {
        if (isEmpty() )
            return -1;
        int minItem = root.element;
        root = merge(root.left, root.right);
        return minItem;
    }
 
    /** Inorder traversal **/
    public void inorder()
    {
        inorder(root);
        System.out.println();
    }
    private void inorder(LeftHeapNode r)
    {
        if (r != null)
        {
            inorder(r.left);
            System.out.print(r.element +" ");
            inorder(r.right);
        }
    }
}
 
/** Class LeftistHeapTest **/
public class LeftistHeapTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("LeftistHeap Test\n\n");        
        LeftistHeap lh = new LeftistHeap();
 
        char ch;
        /**  Perform LeftistHeap operations  **/
        do    
        {
            System.out.println("\nLeftist Heap Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. delete min");
            System.out.println("3. check empty");            
            System.out.println("4. clear");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                lh.insert( scan.nextInt() );                                    
                break;                          
            case 2 : 
                lh.deleteMin();
                break;                         
            case 3 : 
                System.out.println("Empty status = "+ lh.isEmpty());
                break;   
            case 4 : 
                lh.clear();
                break;           
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /** Display heap **/
            System.out.print("\nInorder Traversal : ");
            lh.inorder();  
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');  
    }
}

LeftistHeap Test
 
 
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
24
 
Inorder Traversal : 24
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
6
 
Inorder Traversal : 24 6
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
19
 
Inorder Traversal : 24 6 19
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
94
 
Inorder Traversal : 24 6 94 19
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
5
 
Inorder Traversal : 24 6 94 19 5
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
63
 
Inorder Traversal : 24 6 94 19 5 63
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 94 19 63 6 24
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 94 19 63 24
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 63 24 94
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
2
 
Inorder Traversal : 94 63
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
4
 
Inorder Traversal :
 
Do you want to continue (Type y or n)
 
y
 
Leftist Heap Operations
 
1. insert
2. delete min
3. check empty
4. clear
3
Empty status = true
 
Inorder Traversal :
 
Do you want to continue (Type y or n)
 
n