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.

  1. /**
  2.  *  Java Program to Implement LeftistHeap
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class LeftHeapNode **/    
  8. class LeftHeapNode
  9. {
  10.     int element, sValue;     
  11.     LeftHeapNode left, right;             
  12.  
  13.     public LeftHeapNode(int ele)
  14.     {
  15.         this(ele, null, null);
  16.     }
  17.     public LeftHeapNode(int ele, LeftHeapNode left, LeftHeapNode right)
  18.     {
  19.         this.element = ele;
  20.         this.left = left;
  21.         this.right = right;
  22.         this.sValue = 0;
  23.     }    
  24. }
  25.  
  26. /** Class LeftistHeap **/
  27. class LeftistHeap
  28. {
  29.     private LeftHeapNode root; 
  30.  
  31.     /** Constructor **/
  32.     public LeftistHeap() 
  33.     {
  34.         root = null;
  35.     }
  36.  
  37.     /** Check if heap is empty **/
  38.     public boolean isEmpty() 
  39.     {
  40.         return root == null;
  41.     }
  42.  
  43.     /** Make heap empty **/ 
  44.     public void clear( )
  45.     {
  46.         root = null;
  47.     }
  48.  
  49.     /** Function to insert data **/
  50.     public void insert(int x )
  51.     {
  52.         root = merge(new LeftHeapNode( x ), root);
  53.     }
  54.  
  55.     /** Function merge **/
  56.     public void merge(LeftistHeap rhs)
  57.     {
  58.         if (this == rhs)    
  59.             return;
  60.         root = merge(root, rhs.root);
  61.         rhs.root = null;
  62.     }
  63.  
  64.     /** Function merge **/
  65.     private LeftHeapNode merge(LeftHeapNode x, LeftHeapNode y)
  66.     {
  67.         if (x == null)
  68.             return y;
  69.         if (y == null)
  70.             return x;
  71.         if (x.element > y.element)
  72.         {
  73.             LeftHeapNode temp = x;
  74.             x = y;
  75.             y = temp;
  76.         }
  77.  
  78.         x.right = merge(x.right, y);
  79.  
  80.           if(x.left == null) 
  81.           {
  82.             x.left = x.right;
  83.             x.right = null;         
  84.         } 
  85.         else 
  86.         {
  87.             if(x.left.sValue < x.right.sValue) 
  88.             {
  89.                 LeftHeapNode temp = x.left;
  90.                   x.left = x.right;
  91.                   x.right = temp;
  92.             }
  93.             x.sValue = x.right.sValue + 1;
  94.         }        
  95.         return x;
  96.     }
  97.  
  98.     /** Function to delete minimum element **/
  99.     public int deleteMin( )
  100.     {
  101.         if (isEmpty() )
  102.             return -1;
  103.         int minItem = root.element;
  104.         root = merge(root.left, root.right);
  105.         return minItem;
  106.     }
  107.  
  108.     /** Inorder traversal **/
  109.     public void inorder()
  110.     {
  111.         inorder(root);
  112.         System.out.println();
  113.     }
  114.     private void inorder(LeftHeapNode r)
  115.     {
  116.         if (r != null)
  117.         {
  118.             inorder(r.left);
  119.             System.out.print(r.element +" ");
  120.             inorder(r.right);
  121.         }
  122.     }
  123. }
  124.  
  125. /** Class LeftistHeapTest **/
  126. public class LeftistHeapTest
  127. {
  128.     public static void main(String[] args)
  129.     {
  130.         Scanner scan = new Scanner(System.in);
  131.         System.out.println("LeftistHeap Test\n\n");        
  132.         LeftistHeap lh = new LeftistHeap();
  133.  
  134.         char ch;
  135.         /**  Perform LeftistHeap operations  **/
  136.         do    
  137.         {
  138.             System.out.println("\nLeftist Heap Operations\n");
  139.             System.out.println("1. insert ");
  140.             System.out.println("2. delete min");
  141.             System.out.println("3. check empty");            
  142.             System.out.println("4. clear");
  143.  
  144.             int choice = scan.nextInt();            
  145.             switch (choice)
  146.             {
  147.             case 1 : 
  148.                 System.out.println("Enter integer element to insert");
  149.                 lh.insert( scan.nextInt() );                                    
  150.                 break;                          
  151.             case 2 : 
  152.                 lh.deleteMin();
  153.                 break;                         
  154.             case 3 : 
  155.                 System.out.println("Empty status = "+ lh.isEmpty());
  156.                 break;   
  157.             case 4 : 
  158.                 lh.clear();
  159.                 break;           
  160.             default : 
  161.                 System.out.println("Wrong Entry \n ");
  162.                 break;   
  163.             }
  164.             /** Display heap **/
  165.             System.out.print("\nInorder Traversal : ");
  166.             lh.inorder();  
  167.  
  168.             System.out.println("\nDo you want to continue (Type y or n) \n");
  169.             ch = scan.next().charAt(0);                        
  170.         } while (ch == 'Y'|| ch == 'y');  
  171.     }
  172. }

advertisement
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.