Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 94
Текст из файла (страница 94)
In the next iteration of the for loop, three links occur; their results areshown in Figures 20.3(f)-(h). Figures 20.3(i)-(l) show the result of the next four iterations ofthe for loop.All that remains is to clean up. Once the for loop of lines 3-13 completes, line 14 empties theroot list, and lines 15-19 reconstruct it from the array A. The resulting Fibonacci heap isshown in Figure 20.3(m). After consolidating the root list, FIB-HEAP-EXTRACT-MINfinishes up by decrementing n[H] in line 11 and returning a pointer to the deleted node z inline 12.Observe that if all trees in the Fibonacci heap are unordered binomial trees before FIB-HEAPEXTRACT-MIN is executed, then they are all unordered binomial trees afterward.
There aretwo ways in which trees are changed. First, in lines 3-5 of FIB-HEAP-EXTRACT-MIN, eachchild x of root z becomes a root. By Exercise 20.2-2, each new tree is itself an unorderedbinomial tree. Second, trees are linked by FIB-HEAP-LINK only if they have the samedegree. Since all trees are unordered binomial trees before the link occurs, two trees whoseroots each have k children must have the structure of Uk. The resulting tree therefore has thestructure of Uk+1.We are now ready to show that the amortized cost of extracting the minimum node of an nnode Fibonacci heap is O(D(n)). Let H denote the Fibonacci heap just prior to the FIB-HEAPEXTRACT-MIN operation.The actual cost of extracting the minimum node can be accounted for as follows.
An O(D(n))contribution comes from there being at most D(n) children of the minimum node that areprocessed in FIB-HEAP-EXTRACT-MIN and from the work in lines 1-2 and 14-19 ofCONSOLIDATE. It remains to analyze the contribution from the for loop of lines 3-13. Thesize of the root list upon calling CONSOLIDATE is at most D(n) + t(H) - 1, since it consistsof the original t(H) root-list nodes, minus the extracted root node, plus the children of theextracted node, which number at most D(n). Every time through the while loop of lines 6-12,one of the roots is linked to another, and thus the total amount of work performed in the forloop is at most proportional to D(n) + t(H).
Thus, the total actual work in extracting theminimum node is O(D(n) + t(H)).The potential before extracting the minimum node is t(H) + 2m(H), and the potentialafterward is at most (D(n) + 1) + 2m(H), since at most D(n) + 1 roots remain and no nodesbecome marked during the operation. The amortized cost is thus at mostO(D(n) + t(H)) + ((D(n) + 1) + 2 m(H)) - (t(H) + 2 m(H))= O(D(n)) + O(t(H)) - t(H)= O(D(n)),since we can scale up the units of potential to dominate the constant hidden in O(t(H).Intuitively, the cost of performing each link is paid for by the reduction in potential due to thelink's reducing the number of roots by one. We shall see in Section 20.4 that D(n) = O(lg n),so that the amortized cost of extracting the minimum node is O(lg n).Exercises 20.2-1Show the Fibonacci heap that results from calling FIB-HEAP-EXTRACT-MIN on theFibonacci heap shown in Figure 20.3(m).Exercises 20.2-2Prove that Lemma 19.1 holds for unordered binomial trees, but with property 4′ in place ofproperty 4.Exercises 20.2-3Show that if only the mergeable-heap operations are supported, the maximum degree D(n) inan n-node Fibonacci heap is at most ⌊lg n⌋.Exercises 20.2-4Professor McGee has devised a new data structure based on Fibonacci heaps.
A McGee heaphas the same structure as a Fibonacci heap and supports the mergeable-heap operations. Theimplementations of the operations are the same as for Fibonacci heaps, except that insertionand union perform consolidation as their last step. What are the worst-case running times ofoperations on McGee heaps? How novel is the professor's data structure?Exercises 20.2-5Argue that when the only operations on keys are comparing two keys (as is the case for all theimplementations in this chapter), not all of the mergeable-heap operations can run in O(1)amortized time.20.3 Decreasing a key and deleting a nodeIn 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 Fibonacciheap are unordered binomial trees.
They are close enough, however, that we can bound themaximum degree D(n) by O(lg n). Proving this bound, which we shall do in Section 20.4, willimply that FIB-HEAP-EXTRACT-MIN and FIB-HEAP-DELETE run in O(lg n) amortizedtime.Decreasing a keyIn the following pseudocode for the operation FIB-HEAP-DECREASE-KEY, we assume asbefore that removing a node from a linked list does not change any of the structural fields inthe removed node.FIB-HEAP-DECREASE-KEY(H, x, k)1 if k > key[x]2then error "new key is greater than current key"3 key[x] ← k4 y ← p[x]5 if y ≠ NIL and key[x] < key[y]6then CUT(H, x, y)7CASCADING-CUT(H, y)8 if key[x] < key[min[H]]9then min[H] ← xCUT(H, x, y)1 remove x from the child list of y, decrementing degree[y]2 add x to the root list of H3 p[x] ← NIL4 mark[x] ← FALSECASCADING-CUT(H, y)1 z ← p[y]2 if z ≠ NIL3456then if mark[y] = FALSEthen mark[y] ← TRUEelse CUT(H, y, z)CASCADING-CUT(H, z)The FIB-HEAP-DECREASE-KEY procedure works as follows.
Lines 1-3 ensure that the newkey is no greater than the current key of x and then assign the new key to x. If x is a root or ifkey[x] ≥ key[y], where y is x's parent, then no structural changes need occur, since min-heaporder 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 thehistory of each node. Suppose that the following events have happened to node x:1. at some time, x was a root,2. then x was linked to another node,3. 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. Thefield mark[x] is TRUE if steps 1 and 2 have occurred and one child of x has been cut. TheCUT procedure, therefore, clears mark[x] in line 4, since it performs step 1.
(We can now seewhy line 3 of FIB-HEAP-LINK clears mark[y]: node y is being linked to another node, and sostep 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 timethat y was linked to another node.
Therefore, line 7 of FIB-HEAP-DECREASE-KEYperforms a cascading-cut operation on y. If y is a root, then the test in line 2 ofCASCADING-CUT causes the procedure to just return. If y is unmarked, the procedure marksit in line 4, since its first child has just been cut, and returns. If y is marked, however, it hasjust lost its second child; y is cut in line 5, and CASCADING-CUT calls itself recursively inline 6 on y's parent z.
The CASCADING-CUT procedure recurses its way up the tree untileither a root or an unmarked node is found.Once all the cascading cuts have occurred, lines 8-9 of FIB-HEAP-DECREASE-KEY finishup by updating min[H] if necessary. The only node whose key changed was the node x whosekey 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 withthe Fibonacci heap shown in Figure 20.4(a).
The first call, shown in Figure 20.4(b), involvesno cascading cuts. The second call, shown in Figures 20.4(c)-(e), invokes two cascading cuts.Figure 20.4: Two calls of FIB-HEAP-DECREASE-KEY. (a) The initial Fibonacci heap. (b)The node with key 46 has its key decreased to 15.
The node becomes a root, and its parent(with key 24), which had previously been unmarked, becomes marked. (c)-(e) The node withkey 35 has its key decreased to 5. In part (c), the node, now with key 5, becomes a root. Itsparent, with key 26, is marked, so a cascading cut occurs. The node with key 26 is cut from itsparent and made an unmarked root in (d).
Another cascading cut occurs, since the node withkey 24 is marked as well. This node is cut from its parent and made an unmarked root in part(e). The cascading cuts stop at this point, since the node with key 7 is a root. (Even if thisnode were not a root, the cascading cuts would stop, since it is unmarked.) The result of theFIB-HEAP-DECREASE-KEY operation is shown in part (e), with min[H] pointing to thenew minimum node.We shall now show that the amortized cost of FIB-HEAP-DECREASE-KEY is only O(1).We start by determining its actual cost.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
