Java Program to Implement Binomial Heap

This is a Java Program to implement Binomial Heap. A binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation. This program is based on the implementation by Willem Visser .

Here is the source code of the Java program to implement Binomial 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 Binomial Heap
  3.  */
  4.  
  5. import java.util.Scanner;
  6.  
  7. /* Class BinomialHeapNode */
  8. class BinomialHeapNode
  9. {
  10.     int key, degree;
  11.     BinomialHeapNode parent;
  12.     BinomialHeapNode sibling;
  13.     BinomialHeapNode child;
  14.  
  15.     /* Constructor */
  16.     public BinomialHeapNode(int k) 
  17.     {
  18.         key = k;
  19.         degree = 0;
  20.         parent = null;
  21.         sibling = null;
  22.         child = null;        
  23.     }
  24.     /* Function reverse */
  25.     public BinomialHeapNode reverse(BinomialHeapNode sibl) 
  26.     {
  27.             BinomialHeapNode ret;
  28.             if (sibling != null)
  29.                 ret = sibling.reverse(this);
  30.             else
  31.                 ret = this;
  32.             sibling = sibl;
  33.             return ret;
  34.     }
  35.     /* Function to find min node */
  36.     public BinomialHeapNode findMinNode() 
  37.     {
  38.             BinomialHeapNode x = this, y = this;
  39.             int min = x.key;
  40.  
  41.             while (x != null) {
  42.                 if (x.key < min) {
  43.                     y = x;
  44.                     min = x.key;
  45.                 }
  46.                 x = x.sibling;
  47.             }
  48.  
  49.             return y;
  50.     }
  51.     /* Function to find node with key value */
  52.     public BinomialHeapNode findANodeWithKey(int value) 
  53.     {
  54.             BinomialHeapNode temp = this, node = null;
  55.  
  56.             while (temp != null) 
  57.             {
  58.                 if (temp.key == value) 
  59.                 {
  60.                     node = temp;
  61.                     break;
  62.                 }
  63.                 if (temp.child == null)
  64.                     temp = temp.sibling;
  65.                 else 
  66.                 {
  67.                     node = temp.child.findANodeWithKey(value);
  68.                     if (node == null)
  69.                         temp = temp.sibling;
  70.                     else
  71.                         break;
  72.                 }
  73.             }
  74.  
  75.             return node;
  76.     }
  77.     /* Function to get size */
  78.     public int getSize() 
  79.     {
  80.         return (1 + ((child == null) ? 0 : child.getSize()) + ((sibling == null) ? 0 : sibling.getSize()));
  81.     }
  82. }
  83.  
  84. /* class BinomialHeap */
  85. class BinomialHeap
  86. {
  87.     private BinomialHeapNode Nodes;
  88.     private int size;
  89.  
  90.     /* Constructor */
  91.     public BinomialHeap()
  92.     {
  93.         Nodes = null;
  94.         size = 0;
  95.     }
  96.     /* Check if heap is empty */
  97.     public boolean isEmpty()
  98.     {
  99.         return Nodes == null;
  100.     }
  101.     /* Function to get size */
  102.     public int getSize()
  103.     {
  104.         return size;
  105.     }
  106.     /* clear heap */
  107.     public void makeEmpty()
  108.     {
  109.         Nodes = null;
  110.         size = 0;
  111.     }
  112.     /* Function to insert */        
  113.     public void insert(int value) 
  114.     {
  115.         if (value > 0)
  116.         {
  117.             BinomialHeapNode temp = new BinomialHeapNode(value);
  118.             if (Nodes == null) 
  119.             {
  120.                 Nodes = temp;
  121.                 size = 1;
  122.             } 
  123.             else 
  124.             {
  125.                 unionNodes(temp);
  126.                 size++;
  127.             }
  128.         }
  129.     }
  130.     /* Function to unite two binomial heaps */
  131.     private void merge(BinomialHeapNode binHeap) 
  132.     {
  133.         BinomialHeapNode temp1 = Nodes, temp2 = binHeap;
  134.  
  135.         while ((temp1 != null) && (temp2 != null)) 
  136.         {
  137.             if (temp1.degree == temp2.degree) 
  138.             {
  139.                 BinomialHeapNode tmp = temp2;
  140.                 temp2 = temp2.sibling;
  141.                 tmp.sibling = temp1.sibling;
  142.                 temp1.sibling = tmp;
  143.                 temp1 = tmp.sibling;
  144.             } 
  145.             else 
  146.             {
  147.                 if (temp1.degree < temp2.degree) 
  148.                 {
  149.                     if ((temp1.sibling == null) || (temp1.sibling.degree > temp2.degree)) 
  150.                     {
  151.                         BinomialHeapNode tmp = temp2;
  152.                         temp2 = temp2.sibling;
  153.                         tmp.sibling = temp1.sibling;
  154.                         temp1.sibling = tmp;
  155.                         temp1 = tmp.sibling;
  156.                     }
  157.                     else 
  158.                     {
  159.                         temp1 = temp1.sibling;
  160.                     }
  161.                 }
  162.                 else 
  163.                 {
  164.                     BinomialHeapNode tmp = temp1;
  165.                     temp1 = temp2;
  166.                     temp2 = temp2.sibling;
  167.                     temp1.sibling = tmp;
  168.                     if (tmp == Nodes) 
  169.                     {
  170.                         Nodes = temp1;
  171.                     }
  172.                     else 
  173.                     {
  174.  
  175.                     }
  176.                 }
  177.             }
  178.         }
  179.         if (temp1 == null) 
  180.         {
  181.             temp1 = Nodes;
  182.             while (temp1.sibling != null) 
  183.             {
  184.                 temp1 = temp1.sibling;
  185.             }
  186.             temp1.sibling = temp2;
  187.         } 
  188.         else
  189.         {
  190.  
  191.         }
  192.     }
  193.     /* Function for union of nodes */
  194.     private void unionNodes(BinomialHeapNode binHeap) 
  195.     {
  196.         merge(binHeap);
  197.  
  198.         BinomialHeapNode prevTemp = null, temp = Nodes, nextTemp = Nodes.sibling;
  199.  
  200.         while (nextTemp != null) 
  201.         {
  202.             if ((temp.degree != nextTemp.degree) || ((nextTemp.sibling != null) && (nextTemp.sibling.degree == temp.degree))) 
  203.             {                
  204.                 prevTemp = temp;
  205.                 temp = nextTemp;
  206.             } 
  207.             else
  208.             {
  209.                 if (temp.key <= nextTemp.key) 
  210.                 {
  211.                     temp.sibling = nextTemp.sibling;
  212.                     nextTemp.parent = temp;
  213.                     nextTemp.sibling = temp.child;
  214.                     temp.child = nextTemp;
  215.                     temp.degree++;
  216.                 } 
  217.                 else 
  218.                 {
  219.                     if (prevTemp == null) 
  220.                     {
  221.                         Nodes = nextTemp;
  222.                     }
  223.                     else 
  224.                     {
  225.                         prevTemp.sibling = nextTemp;
  226.                     }
  227.                     temp.parent = nextTemp;
  228.                     temp.sibling = nextTemp.child;
  229.                     nextTemp.child = temp;
  230.                     nextTemp.degree++;
  231.                     temp = nextTemp;
  232.                 }
  233.             }
  234.             nextTemp = temp.sibling;
  235.         }
  236.     }
  237.     /* Function to return minimum key */
  238.     public int findMinimum() 
  239.     {
  240.         return Nodes.findMinNode().key;
  241.     }
  242.     /* Function to delete a particular element */
  243.     public void delete(int value) 
  244.     {
  245.         if ((Nodes != null) && (Nodes.findANodeWithKey(value) != null)) 
  246.         {
  247.             decreaseKeyValue(value, findMinimum() - 1);
  248.             extractMin();
  249.         }
  250.     }
  251.     /* Function to decrease key with a given value */
  252.     public void decreaseKeyValue(int old_value, int new_value) 
  253.     {
  254.         BinomialHeapNode temp = Nodes.findANodeWithKey(old_value);
  255.         if (temp == null)
  256.             return;
  257.         temp.key = new_value;
  258.         BinomialHeapNode tempParent = temp.parent;
  259.  
  260.         while ((tempParent != null) && (temp.key < tempParent.key)) 
  261.         {
  262.             int z = temp.key;
  263.             temp.key = tempParent.key;
  264.             tempParent.key = z;
  265.  
  266.             temp = tempParent;
  267.             tempParent = tempParent.parent;
  268.         }
  269.     }
  270.     /* Function to extract the node with the minimum key */
  271.     public int extractMin() 
  272.     {
  273.         if (Nodes == null)
  274.             return -1;
  275.  
  276.         BinomialHeapNode temp = Nodes, prevTemp = null;
  277.         BinomialHeapNode minNode = Nodes.findMinNode();
  278.  
  279.         while (temp.key != minNode.key) 
  280.         {
  281.             prevTemp = temp;
  282.             temp = temp.sibling;
  283.         }
  284.  
  285.         if (prevTemp == null) 
  286.         {
  287.             Nodes = temp.sibling;
  288.         }
  289.         else
  290.         {
  291.             prevTemp.sibling = temp.sibling;
  292.         }
  293.  
  294.         temp = temp.child;
  295.         BinomialHeapNode fakeNode = temp;
  296.  
  297.         while (temp != null) 
  298.         {
  299.             temp.parent = null;
  300.             temp = temp.sibling;
  301.         }
  302.  
  303.         if ((Nodes == null) && (fakeNode == null))
  304.         {
  305.             size = 0;
  306.         } 
  307.         else
  308.         {
  309.             if ((Nodes == null) && (fakeNode != null)) 
  310.             {
  311.                 Nodes = fakeNode.reverse(null);
  312.                 size = Nodes.getSize();
  313.             }
  314.             else
  315.             {
  316.                 if ((Nodes != null) && (fakeNode == null))
  317.                 {
  318.                     size = Nodes.getSize();
  319.                 }
  320.                 else
  321.                 {
  322.                     unionNodes(fakeNode.reverse(null));
  323.                     size = Nodes.getSize();
  324.                 }
  325.             }
  326.         }
  327.  
  328.         return minNode.key;
  329.     }
  330.  
  331.     /* Function to display heap */
  332.     public void displayHeap()
  333.     {
  334.         System.out.print("\nHeap : ");
  335.         displayHeap(Nodes);
  336.         System.out.println("\n");
  337.     }
  338.     private void displayHeap(BinomialHeapNode r)
  339.     {
  340.         if (r != null)
  341.         {
  342.             displayHeap(r.child);
  343.             System.out.print(r.key +" ");
  344.             displayHeap(r.sibling);
  345.         }
  346.     }    
  347. }    
  348.  
  349.  
  350. /* Class BinomialHeapTest */
  351. public class BinomialHeapTest
  352. {
  353.     public static void main(String[] args)
  354.     {
  355.         Scanner scan = new Scanner(System.in);
  356.         System.out.println("Binomial Heap Test\n\n");
  357.  
  358.         /* Make object of BinomialHeap */
  359.         BinomialHeap bh = new BinomialHeap( );
  360.  
  361.         char ch;
  362.         /*  Perform BinomialHeap operations  */
  363.         do    
  364.         {
  365.             System.out.println("\nBinomialHeap Operations\n");
  366.             System.out.println("1. insert ");
  367.             System.out.println("2. delete ");
  368.             System.out.println("3. size");            
  369.             System.out.println("4. check empty");
  370.             System.out.println("5. clear");
  371.  
  372.             int choice = scan.nextInt();            
  373.             switch (choice)
  374.             {
  375.             case 1 : 
  376.                 System.out.println("Enter integer element to insert");
  377.                 bh.insert( scan.nextInt() ); 
  378.                 break;                          
  379.             case 2 :     
  380.                 System.out.println("Enter element to delete ");            
  381.                 bh.delete( scan.nextInt() );   
  382.                 break;                         
  383.             case 3 : 
  384.                 System.out.println("Size = "+ bh.getSize());
  385.                 break;                                   
  386.             case 4 : 
  387.                 System.out.println("Empty status = "+ bh.isEmpty());
  388.                 break; 
  389.             case 5 : 
  390.                 bh.makeEmpty();
  391.                 System.out.println("Heap Cleared\n");
  392.                 break;         
  393.             default :  
  394.                 System.out.println("Wrong Entry \n ");
  395.                 break;   
  396.             }
  397.             /* Display heap */ 
  398.             bh.displayHeap();  
  399.  
  400.             System.out.println("\nDo you want to continue (Type y or n) \n");
  401.             ch = scan.next().charAt(0);                        
  402.         } while (ch == 'Y'|| ch == 'y');  
  403.     }
  404. }

Binomial Heap Test
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
1
Enter integer element to insert
73
 
Heap : 73
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
1
Enter integer element to insert
19
 
Heap : 73 19
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
1
Enter integer element to insert
24
 
Heap : 24 73 19
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
1
Enter integer element to insert
51
 
Heap : 51 24 73 19
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
1
Enter integer element to insert
99
 
Heap : 99 51 24 73 19
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
3
Size = 5
 
Heap : 99 51 24 73 19
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
2
Enter element to delete
51
 
Heap : 99 73 24 19
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
5
Heap Cleared
 
 
Heap :
 
 
Do you want to continue (Type y or n)
 
y
 
BinomialHeap Operations
 
1. insert
2. delete
3. size
4. check empty
5. clear
4
Empty status = true
 
Heap :
 
 
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 & discussions at Telegram SanfoundryClasses.