19-3 More Fibonacci-heap operations

We wish to augment a Fibonacci heap HH 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)\text{FIB-HEAP-CHANGE-KEY}(H, x, k) changes the key of node xx to the value kk. Give an efficient implementation of FIB-HEAP-CHANGE-KEY\text{FIB-HEAP-CHANGE-KEY}, and analyze the amortized running time of your implementation for the cases in which kk is greater than, less than, or equal to x.keyx.key.

b. Give an efficient implementation of FIB-HEAP-PRUNE(H,r)\text{FIB-HEAP-PRUNE}(H, r), which deletes q=min(r,H.n)q = \min(r, H.n) nodes from HH. You may choose any qq nodes to delete. Analyze the amortized running time of your implementation. (Hint:\textit{Hint:} You may need to modify the data structure and potential function.)

a. If k<x.keyk < x.key just run the decrease key procedure. If k>x.keyk > x.key, delete the current value xx and insert xx again with a new key. For the first case, the amortized time is O(1)O(1), and for the last case the amortized time is O(lgn)O(\lg n).

b. Suppose that we also had an additional cost to the potential function that was proportional to the size of the structure. This would only increase when we do an insertion, and then only by a constant amount, so there aren't any worries concerning this increased potential function raising the amortized cost of any operations. Once we've made this modification, to the potential function, we also modify the heap itself by having a doubly linked list along all of the leaf nodes in the heap.

To prune we then pick any leaf node, remove it from it's parent's child list, and remove it from the list of leaves. We repeat this min(r,H.n)\min(r, H.n) times. This causes the potential to drop by an amount proportional to rr which is on the order of the actual cost of what just happened since the deletions from the linked list take only constant amounts of time each. So, the amortized time is constant.