Homework 9: Amortized Analysis and Fibonacci Heaps
Problems
- Exercise 17.3-3.(Hint: a reasonable potential function to use is Φ(Di) = kni · lnni where ni is the number of elements in the binary heap, and k is a big enough constant. You can use this function and just show the change in potential for each of the two operations.)
- Exercise 17.3-6.
- Exercise 19.2-1
- . Implement binomial heaps as described in class and in the book. You should use links (pointers) to implement the structure as shown in the figure 1. Your implementation should include the operations: Make-heap, Insert, Minimum, Extract- Min, Union, Decrease-Key, DeleteFigure 1: binomial heaps
Make sure to preserve the characteristics of binomial heaps at all times: (1) each component should be a binomial tree with children-keys bigger than the parent-key;
1
(2) the binomial trees should be in order of size from left to right. Test your code several arrays set of random generated integers (keys).
- (Extra Credit) Find a way to nicely draw the binomial heap created from input, like in the figure.
- (Extra Credit). Write code to implement Fibonacci Heaps, with discussed operations: ExtractMin, Union, Consolidate, DecreseKey, Delete.
- (Extra Credit). Figure out what are the marked nodes on Fibonacci Heaps. In partic- ular explain how the potential function works for FIB-HEAP-EXTRACT-MEAN and FIB- HEAP-DECREASE-KEY operations.
2
