[SOLVED] CS2094D Assignment 4

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 5

    Sample Output:

50 10 30 20 40 10
10
20 30 50 40

46
20 30 46 40 -1

2