Decreasing a key and deleting a node: In this section, we show how to decrease the key of a node in a Fibonacci heap in O(1) amortized time and how to delete any node from an n-node Fibonacci heap in O(D(n)) amortized time. These operations do not preserve the property that all trees in the Fibonacci heap are unordered binomial trees. They are close enough, however, that we can bound the maximum degree D(n) by O(lg n).
In the following pseudocode for the operation FIB-HEAP-DECREASE-KEY, we assume as before that removing a node from a linked list does not change any of the structural fields in the removed node.
FIB-HEAP-DECREASE-KEY(H, x, k) 1 if k > key[x] 2 then error "new key is greater than current key" 3 key[x] ← k 4 y ← p[x] 5 if y ≠ NIL and key[x] < key[y] 6 then CUT(H, x, y) 7 CASCADING-CUT(H, y) 8 if key[x] < key[min[H]] 9 then min[H] ← x
CUT(H, x, y) 1 remove x from the child list of y, decrementing degree[y] 2 add x to the root list of H 3 p[x] ← NIL 4 mark[x] ← FALSE
CASCADING-CUT(H, y) 1 z ← p[y] 2 if z ≠ NIL 3 then if mark[y] = FALSE 4 then mark[y] ← TRUE 5 else CUT(H, y, z) 6 CASCADING-CUT(H, z)
The FIB-HEAP-DECREASE-KEY procedure works as follows. Lines 1-3 ensure that the new key is no greater than the current key of x and then assign the new key to x. If x is a root or if key[x] ≥ key[y], where y is x's parent, then no structural changes need occur, since min-heap order has not been violated. Lines 4-5 test for this condition.
If min-heap order has been violated, many changes may occur. We start by cutting x in line 6. The CUT procedure "cuts" the link between x and its parent y, making x a root.
We use the mark fields to obtain the desired time bounds. They record a little piece of the history of each node. Suppose that the following events have happened to node x:
at some time, x was a root,
then x was linked to another node,
then two children of x were removed by cuts.
As soon as the second child has been lost, we cut x from its parent, making it a new root. The field mark[x] is TRUE if steps 1 and 2 have occurred and one child of x has been cut. The CUT procedure, therefore, clears mark[x] in line 4, since it performs step 1. (We can now see why line 3 of FIB-HEAP-LINK clears mark[y]: node y is being linked to another node, and so step 2 is being performed. The next time a child of y is cut, mark[y] will be set to TRUE.)
We are not yet done, because x might be the second child cut from its parent y since the time that y was linked to another node. Therefore, line 7 of FIB-HEAP-DECREASE-KEY performs a cascading-cut operation on y. If y is a root, then the test in line 2 of CASCADING-CUT causes the procedure to just return. If y is unmarked, the procedure marks it in line 4, since its first child has just been cut, and returns. If y is marked, however, it has just lost its second child; y is cut in line 5, and CASCADING-CUT calls itself recursively in line 6 on y's parent z. The CASCADING-CUT procedure recurses its way up the tree until either a root or an unmarked node is found.
Once all the cascading cuts have occurred, lines 8-9 of FIB-HEAP-DECREASE-KEY finish up by updating min[H] if necessary. The only node whose key changed was the node x whose key decreased. Thus, the new minimum node is either the original minimum node or node x.
Figure 20.4 shows the execution of two calls of FIB-HEAP-DECREASE-KEY, starting with the Fibonacci heap shown in Figure 20.4(a). The first call, shown in Figure 20.4(b), involves no cascading cuts. The second call, shown in Figures 20.4(c)-(e), invokes two cascading cuts.
