Solution Found!
More Fibonacci-heap operations We wish to augment a
Chapter 19, Problem 19-3(choose chapter or problem)
We wish to augment a Fibonacci heap H to support two new operations without changing the amortized running time of any other Fibonacci-heap operations.
a. The operation FIB-HEAP-CHANGE-KEY(H, x, k) changes the key of node x to the value k. Give an efficient implementation of FIB-HEAP-CHANGE-KEY, and analyze the amortized running time of your implementation for the cases in which k is greater than, less than, or equal to x.key.
b. Give an efficient implementation of FIB-HEAP-PRUNE (H, r), which deletes q = min(r , H . n) nodes from H. You may choose any q nodes to delete. Analyze the amortized running time of your implementation. (Hint: You may need to modify the data structure and potential function.)
Questions & Answers
QUESTION:
We wish to augment a Fibonacci heap H to support two new operations without changing the amortized running time of any other Fibonacci-heap operations.
a. The operation FIB-HEAP-CHANGE-KEY(H, x, k) changes the key of node x to the value k. Give an efficient implementation of FIB-HEAP-CHANGE-KEY, and analyze the amortized running time of your implementation for the cases in which k is greater than, less than, or equal to x.key.
b. Give an efficient implementation of FIB-HEAP-PRUNE (H, r), which deletes q = min(r , H . n) nodes from H. You may choose any q nodes to delete. Analyze the amortized running time of your implementation. (Hint: You may need to modify the data structure and potential function.)
ANSWER:Step 1 of 11
Augmentation of Fibonacci heap
Fibonacci heap is a structural model which is a grouping of several heaps. Fibonacci heap performs all the operations of mergeable heap. One more property of Fibonacci heap is that the time taken operations is constant amortized. They have a better running time than the normal binomial heap. Fibonacci heap is composed of a set of heaps. Every heap fulfills the minimum requirement of a minheap.