19-3.md

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 $\text{FIB-HEAP-CHANGE-KEY}(H, x, k)$ changes the key of node $x$ to the value $k$. Give an efficient implementation of $\text{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 $\text{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. ($\textit{Hint:}$ You may need to modify the data structure and potential function.)

a. If $k < x.key$ just run the decrease key procedure. If $k > x.key$, delete the current value $x$ and insert $x$ again with a new key. For the first case, the amortized time is $O(1)$, and for the last case the amortized time is $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)$ times. This causes the potential to drop by an amount proportional to $r$ 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.