you need to implement the Binomial (Min) Heap data structure. It must support the following operations.
1. Find-Min : Returns the node having the minimum key
2. Extract-Mi : Returns the node having the minimum key and deletes it from the heap
3. Insert : Inserts a new node in the heap
4. Union : Merges two binomial heaps
5. Print : Prints the level order traversal with level no. of each of the binomial trees in the heap
Input/Output:
You will take input from a text file where each line will specify one of the aforementioned operations. The operations are denoted by the first letter i.e. 'F' indicates Find-Min operation, 'I' indicates Insert operation and so on. Then the operands will follow where necessary. You can assume that all the operands will be integers.
You have to print the output to a text file. Keep provision of printing output to the console as well (but printing both to file and to console simultaneously will not be necessary).
Check out the Sample I/O for further clarification.
Sample I/O:
Input
Output
I 5
I 2
P
I 10
P
F
E
P
U 3 20
P
Printing Binomial Heap...
Binomial Tree, B1
Level 0 : 2
Level 1 : 5
Printing Binomial Heap...
Binomial Tree, B0 Level 0 : 10
Binomial Tree, B1
Level 0 : 2
Level 1 : 5
Find-Min returned 2 Extract-Min returned 2 Printing Binomial Heap...
Binomial Tree, B1
Level 0 : 5
Level 1 : 10
Printing Binomial Heap...
Binomial Tree, B2
Level 0 : 3
Level 1 : 5 20
Level 2 : 10
Note that, the operands of Union operation indicates the keys with which you should construct a new binomial heap and then merge it with the existing one. For example, when U 3 20 is given, a
binomial heap is constructed with 3 and 20 and then merged with the existing one containing 5 and 10. So the existing binomial heap is updated after an Union operation.
