Problems 20-2: More Fibonacci-heap operations
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 key[x]. (b)Give an efficient implementation of FIB-HEAP-PRUNE(H, r), which deletes min(r, n[H]) nodes from H. Which nodes are deleted should be arbitrary. Analyze the amortized running time of your implementation. (Hint: You may need to modify the data structure and potential function.) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
