Description
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.
-
Present the time complexity of each operation.
-
Comparing the Fibonacci heap to the simple min-heap and identify the advantages and disadvan-tages of Fibonacci heap.
-
Explain in which circumstances Fibonacci heaps should be preferred over other types of heap.
