Java Program to Implement Meldable Heap

«
»
This is a Java Program to Implement Meldable Heap. A randomized meldable heap (also Meldable Heap or Randomized Meldable Priority Queue) is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree. However, there are no restrictions on the shape of the underlying binary tree.

Here is the source code of the Java Program to Implement Meldable 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 Meldable Heap
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.Random;
  7.  
  8. /** Class Node **/
  9. class Node
  10. {
  11.     Node left, right, parent;
  12.     int x;
  13.  
  14.     public Node(Node parent, Node left, Node right, int x)
  15.     {
  16.         this.parent = parent;
  17.         this.left = left;
  18.         this.right = right;
  19.         this.x = x;
  20.     }
  21. }
  22.  
  23. /** Class MedlableHeap **/
  24. class MeldableHeap
  25. {
  26.     private Random rand;
  27.     private int n;    
  28.     private Node root;
  29.  
  30.     public MeldableHeap()
  31.     {
  32.         root = null;
  33.         rand = new Random();
  34.         n = 0;
  35.     }
  36.  
  37.     /** Check if heap is empty **/
  38.     public boolean isEmpty()
  39.     {
  40.         return root == null;
  41.     }
  42.  
  43.     /** clear heap **/
  44.     public void makeEmpty()
  45.     {
  46.         root = null;
  47.         rand = new Random();
  48.         n = 0;
  49.     }
  50.  
  51.     /** function to get size **/
  52.     public int getSize()
  53.     {
  54.         return n;
  55.     }
  56.  
  57.     /** function to insert an element **/
  58.     public void add(int x) 
  59.     {
  60.         Node u = new Node(null, null, null, x);
  61.         root = meld(u, root);
  62.         root.parent = null;
  63.         n++;
  64.     }
  65.  
  66.     /** function to remove an element **/
  67.     public int remove() 
  68.     {
  69.         int x = root.x;
  70.         root = meld(root.left, root.right);
  71.         if (root != null) 
  72.             root.parent = null;
  73.         n--;
  74.         return x;
  75.     }
  76.  
  77.     /** function to merge two nodes **/
  78.     public Node meld(Node q1, Node q2) 
  79.     {
  80.         if (q1 == null) 
  81.             return q2;
  82.         if (q2 == null) 
  83.             return q1;
  84.  
  85.         if (q2.x < q1.x) 
  86.             return meld(q2, q1);
  87.  
  88.         if (rand.nextBoolean()) 
  89.         {
  90.             q1.left = meld(q1.left, q2);
  91.             q1.left.parent = q1;
  92.         } 
  93.         else 
  94.         {
  95.             q1.right = meld(q1.right, q2);
  96.             q1.right.parent = q1;
  97.         }
  98.         return q1;
  99.     }
  100.  
  101.     /** function to print heap **/
  102.     public void displayHeap()
  103.     {
  104.         System.out.print("\nMeldable Heap : ");
  105.         if (root == null)
  106.         {
  107.             System.out.print("Empty\n");
  108.             return;
  109.         }
  110.  
  111.         Node prev, w = root;
  112.         while (w.left != null) 
  113.             w = w.left;
  114.  
  115.         while (w != null)
  116.         {
  117.             System.out.print(w.x +" ");
  118.             prev = w;
  119.             w = nextNode(w);            
  120.         }
  121.         System.out.println();
  122.     }
  123.  
  124.     /** function to get next node in heap **/
  125.     private Node nextNode(Node w) 
  126.     {
  127.         if (w.right != null) 
  128.         {
  129.             w = w.right;
  130.             while (w.left != null)
  131.                 w = w.left;
  132.         } 
  133.         else 
  134.         {
  135.             while (w.parent != null && w.parent.left != w)
  136.                 w = w.parent;
  137.             w = w.parent;
  138.         }
  139.         return w;
  140.     }    
  141. }
  142.  
  143. /** Class MeldableHeapTest **/
  144. public class MeldableHeapTest
  145. {
  146.     public static void main(String[] args)
  147.     {
  148.         Scanner scan = new Scanner(System.in);
  149.         System.out.println("Meldable Heap Test\n\n");
  150.  
  151.         /* Make object of MeldableHeap */
  152.         MeldableHeap mh = new MeldableHeap();
  153.  
  154.         char ch;
  155.         /*  Perform Meldable Heap operations  */
  156.         do    
  157.         {
  158.             System.out.println("\nMeldable Heap Operations\n");
  159.             System.out.println("1. add");
  160.             System.out.println("2. remove");
  161.             System.out.println("3. size");            
  162.             System.out.println("4. check empty");
  163.             System.out.println("5. clear");
  164.  
  165.             int choice = scan.nextInt();            
  166.             switch (choice)
  167.             {
  168.             case 1 : 
  169.                 System.out.println("Enter integer element to insert");
  170.                 mh.add( scan.nextInt() ); 
  171.                 break;                          
  172.             case 2 :                 
  173.                 System.out.println("Removed Element : "+ mh.remove() );  
  174.                 break;                         
  175.             case 3 : 
  176.                 System.out.println("Size = "+ mh.getSize());
  177.                 break;                                   
  178.             case 4 : 
  179.                 System.out.println("Empty status = "+ mh.isEmpty());
  180.                 break; 
  181.             case 5 : 
  182.                 mh.makeEmpty();
  183.                 System.out.println("Heap Cleared\n");
  184.                 break;         
  185.             default : 
  186.                 System.out.println("Wrong Entry \n ");
  187.                 break;   
  188.             }
  189.             /* Display heap */
  190.             mh.displayHeap();  
  191.  
  192.             System.out.println("\nDo you want to continue (Type y or n) \n");
  193.             ch = scan.next().charAt(0);                        
  194.         } while (ch == 'Y'|| ch == 'y');  
  195.     }
  196. }

advertisement
Meldable Heap Test
 
 
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
4
Empty status = true
 
Meldable Heap : Empty
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
24
 
Meldable Heap : 24
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
6
 
Meldable Heap : 24 6
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
28
 
Meldable Heap : 28 24 6
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
94
 
Meldable Heap : 28 24 6 94
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
19
 
Meldable Heap : 28 24 6 19 94
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
5
 
Meldable Heap : 28 24 6 19 94 5
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
63
 
Meldable Heap : 28 24 6 19 94 5 63
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
3
Size = 7
 
Meldable Heap : 28 24 6 19 94 5 63
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
2
Removed Element : 5
 
Meldable Heap : 28 63 24 6 19 94
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
2
Removed Element : 6
 
Meldable Heap : 28 63 24 19 94
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
2
Removed Element : 19
 
Meldable Heap : 28 63 24 94
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
2
Removed Element : 24
 
Meldable Heap : 94 28 63
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
5
Heap Cleared
 
 
Meldable Heap : Empty
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
4
Empty status = true
 
Meldable Heap : Empty
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
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.