QUESTIONS
1. Write a program to implement a Binomial Heap and perform the operations insertion, deletion, extract minimum and union. Your program should contain the following functions:
- MakeHeap() – Creates and returns a new heap H containing no elements.
- Insert(H, x) – Inserts a new node with key ‘x’ into the heap H.
- Minimum(H) – Return the value of the smallest key in the heap H.
- ExtractMin(H) – Deletes the node with minimum key value from heap H and prints the deleted node.
- DecreaseKey(H, x, k) – If the node of H with key ‘x’ is at least ‘k’, then decreases the value of node with key ‘x’ by ‘k’. Otherwise, it prints -1.
- Delete(H, x) – Deletes the node with key ‘x’ from the heap H. If node is present, it prints the deleted node else it prints -1.
- Union(H1, H2) – Create and return a new heap H that contains all the nodes of heaps H1 and H2. Heaps H1 and H2 are “destroyed” by this operation.
Input Format:
- Each line contains a character from ‘i’, ‘m’, ‘x’, ‘r’, ‘d’ and ‘e’ followed by at most one integer. The integers, if given, are in the range [−106,106].
- ik-insertskintotheheap
- d k – deletes the node with key k from the heap and print the deleted node’s key.
- p – prints the binomial heap
- m – prints the minimum element in the binomial heap (Note:- In print function, level order traversal is to be used).
- x – extracts and prints the minimum element from the heap
- ryz-decreasesthevalueofnodewithkeyybyz.
- e – ‘exit’ from the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
Sample Input:
i 10 i 20 i 30 i 40 i 50 p m x
p
r 50 4 p
r 70 5Sample Output:
50 10 30 20 40 10
10
20 30 50 40
46
20 30 46 40 -1
2
