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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!