Goals of the lab
• Course application
• Data sctructures
• Python Object Oriented Programming
Unless specified otherwise, all the programs are expected to be completed in Python or O’caml.
1. In a class implement all the following operations for the Fibonacci Heap data structure.
• MakeHeap • ExtractMin • Delete
• Insert • Union
• Minimum • DecreaseKey
Note: define a clean and clear API as Fibonacci Heaps are to be reused in a future lab.
2. Present the time complexity of each operation.
3. Comparing the Fibonacci heap to the simple min-heap and identify the advantages and disadvan-tages of Fibonacci heap.
4. Explain in which circumstances Fibonacci heaps should be preferred over other types of heap.
