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.