Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 95
Текст из файла (страница 95)
The FIB-HEAP-DECREASE-KEY procedure takesO(1) time, plus the time to perform the cascading cuts. Suppose that CASCADING-CUT isrecursively called c times from a given invocation of FIB-HEAP-DECREASE-KEY. Eachcall of CASCADING-CUT takes O(1) time exclusive of recursive calls. Thus, the actual costof FIB-HEAP-DECREASE-KEY, including all recursive calls, is O(c).We next compute the change in potential.
Let H denote the Fibonacci heap just prior to theFIB-HEAP-DECREASE-KEY operation. Each recursive call of CASCADING-CUT, exceptfor the last one, cuts a marked node and clears the mark bit. Afterward, there are t(H)+c trees(the original t(H) trees, c-1 trees produced by cascading cuts, and the tree rooted at x) and atmost m(H) - c +2 marked nodes (c-1 were unmarked by cascading cuts and the last call ofCASCADING-CUT may have marked a node). The change in potential is therefore at most((t(H) + c) + 2(m(H) - c + 2)) - (t(H) + 2m(H)) = 4 - c.Thus, the amortized cost of FIB-HEAP-DECREASE-KEY is at mostO(c) + 4 - c = O(1),since we can scale up the units of potential to dominate the constant hidden in O(c).You can now see why the potential function was defined to include a term that is twice thenumber of marked nodes.
When a marked node y is cut by a cascading cut, its mark bit iscleared, so the potential is reduced by 2. One unit of potential pays for the cut and the clearingof the mark bit, and the other unit compensates for the unit increase in potential due to node ybecoming a root.Deleting a nodeIt is easy to delete a node from an n-node Fibonacci heap in O(D(n)) amortized time, as isdone by the following pseudocode. We assume that there is no key value of -∞ currently inthe Fibonacci heap.FIB-HEAP-DELETE(H, x)1 FIB-HEAP-DECREASE-KEY(H, x, -∞)2 FIB-HEAP-EXTRACT-MIN(H)FIB-HEAP-DELETE is analogous to BINOMIAL-HEAP-DELETE. It makes x become theminimum node in the Fibonacci heap by giving it a uniquely small key of -∞.
Node x is thenremoved from the Fibonacci heap by the FIB-HEAP-EXTRACT-MIN procedure. Theamortized time of FIB-HEAP-DELETE is the sum of the O(1) amortized time of FIB-HEAPDECREASE-KEY and the O(D(n)) amortized time of FIB-HEAP-EXTRACT-MIN. Since weshall see in Section 20.4 that D(n) = O(lg n), the amortized time of FIB-HEAP-DELETE isO(lg n).Exercises 20.3-1Suppose that a root x in a Fibonacci heap is marked. Explain how x came to be a marked root.Argue that it doesn't matter to the analysis that x is marked, even though it is not a root thatwas first linked to another node and then lost one child.Exercises 20.3-2Justify the O(1) amortized time of FIB-HEAP-DECREASE-KEY as an average cost peroperation by using aggregate analysis.20.4 Bounding the maximum degreeTo prove that the amortized time of FIB-HEAP-EXTRACT-MIN and FIB-HEAP-DELETE isO(lg n), we must show that the upper bound D(n) on the degree of any node of an n-nodeFibonacci heap is O(lg n).
By Exercise 20.2-3, when all trees in the Fibonacci heap areunordered binomial trees, D(n) = ⌊lg n⌋. The cuts that occur in FIB-HEAP-DECREASEKEY, however, may cause trees within the Fibonacci heap to violate the unordered binomialtree properties. In this section, we shall show that because we cut a node from its parent assoon as it loses two children, D(n) is O(lg n).
In particular, we shall show that D(n) ≤ ⌊logφn⌋,.whereThe key to the analysis is as follows. For each node x within a Fibonacci heap, define size(x)to be the number of nodes, including x itself, in the subtree rooted at x. (Note that x need notbe in the root list-it can be any node at all.) We shall show that size(x) is exponential indegree[x]. Bear in mind that degree[x] is always maintained as an accurate count of thedegree of x.Lemma 20.1Let x be any node in a Fibonacci heap, and suppose that degree[x] = k. Let y1, y2, . . . , ykdenote the children of x in the order in which they were linked to x, from the earliest to thelatest. Then, degree[y1] ≥ 0 and degree[yi] ≥ i - 2 for i = 2, 3, .
. . , k.Proof Obviously, degree[y1] ≥ 0.For i ≥ 2, we note that when yi was linked to x, all of y1, y2, . . . , yi-1 were children of x, so wemust have had degree[x] = i - 1. Node yi is linked to x only if degree[x] = degree[yi], so wemust have also had degree[yi] = i - 1 at that time. Since then, node yi has lost at most onechild, since it would have been cut from x if it had lost two children. We conclude thatdegree[yi ] ≥ i - 2.We finally come to the part of the analysis that explains the name "Fibonacci heaps." Recallfrom Section 3.2 that for k = 0, 1, 2, .
. . , the kth Fibonacci number is defined by therecurrenceThe following lemma gives another way to express Fk.Lemma 20.2For all integers k ≥ 0,Proof The proof is by induction on k. When k = 0,We now assume the inductive hypothesis that, and we haveThe following lemma and its corollary complete the analysis. They use the in-equality(proved in Exercise 3.2-7)Fk+2 ≥ φk,where φ is the golden ratio, defined in equation (3.22) as.Lemma 20.3Let x be any node in a Fibonacci heap, and let k = degree[x]. Then, size(x) ≥ Fk+2 ≥ φk, where.Proof Let sk denote the minimum possible value of size(z) over all nodes z such that degree[z]= k. Trivially, s0 = 1, s1 = 2, and s2 = 3. The number sk is at most size(x), and clearly, the valueof sk increases monotonically with k.
As in Lemma 20.1, let y1, y2, . . . , yk denote the childrenof x in the order in which they were linked to x. To compute a lower bound on size(x), wecount one for x itself and one for the first child y1 (for which size(y1) ≥ 1), givingwhere the last line follows from Lemma 20.1 (so that degree[yi] ≥ i - 2) and the monotonicityof sk (so that sdegree [yi] ≥ si-2).We now show by induction on k that sk ≥ Fk+2 for all nonnegative integer k. The bases, for k =0 and k = 1, are trivial.
For the inductive step, we assume that k ≥ 2 and that si ≥ Fi+2 for i = 0,1, . . . , k - 1. We haveThus, we have shown that size(x) ≥ sk ≥ Fk+2 ≥ φk.Corollary 20.4The maximum degree D(n) of any node in an n-node Fibonacci heap is O(lg n).Proof Let x be any node in an n-node Fibonacci heap, and let k = degree[x]. By Lemma 20.3,we have n ≥ size(x) ≥ φk. Taking base-φ logarithms gives us k ≤ logφ n. (In fact, because k isan integer, k ≤ ⌊logφ n⌋.) The maximum degree D(n) of any node is thus O(lg n).Exercises 20.4-1Professor Pinocchio claims that the height of an n-node Fibonacci heap is O(lg n).
Show thatthe professor is mistaken by exhibiting, for any positive integer n, a sequence of Fibonacciheap operations that creates a Fibonacci heap consisting of just one tree that is a linear chainof n nodes.Exercises 20.4-2Suppose we generalize the cascading-cut rule to cut a node x from its parent as soon as it losesits kth child, for some integer constant k. (The rule in Section 20.3 uses k = 2.) For whatvalues of k is D(n) = O(lg n)?Problems 20-1: Alternative implementation of deletionProfessor Pisano has proposed the following variant of the FIB-HEAP-DELETE procedure,claiming that it runs faster when the node being deleted is not the node pointed to by min[H].PISANO-DELETE(H, x)1 if x = min[H]2then FIB-HEAP-EXTRACT-MIN(H)3else y ← p[x]4if y ≠ NIL5then CUT(H, x, y)6CASCADING-CUT(H, y)7add x's child list to the root list of H8remove x from the root list of Ha.
The professor's claim that this procedure runs faster is based partly on the assumptionthat line 7 can be performed in O(1) actual time. What is wrong with this assumption?b. Give a good upper bound on the actual time of PISANO-DELETE when x is notmin[H]. Your bound should be in terms of degree[x] and the number c of calls to theCASCADING-CUT procedure.c. Suppose that we call PISANO-DELETE(H, x), and let H′ be the Fibonacci heap thatresults.
Assuming that node x is not a root, bound the potential of H′ in terms ofdegree[x], c, t(H), and m(H).d. Conclude that the amortized time for PISANO-DELETE is asymptotically no betterthan for FIB-HEAP-DELETE, even when x ≠ min[H].Problems 20-2: More Fibonacci-heap operationsWe wish to augment a Fibonacci heap H to support two new operations without changing theamortized 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 thevalue k. Give an efficient implementation of FIB-HEAP-CHANGE-KEY, and analyzethe amortized running time of your implementation for the cases in which k is greaterthan, less than, or equal to key[x].b. Give an efficient implementation of FIB-HEAP-PRUNE(H, r), which deletes min(r,n[H]) nodes from H. Which nodes are deleted should be arbitrary. Analyze theamortized running time of your implementation. (Hint: You may need to modify thedata structure and potential function.)Chapter notesFibonacci heaps were introduced by Fredman and Tarjan [98]. Their paper also describes theapplication of Fibonacci heaps to the problems of single-source shortest paths, all-pairsshortest paths, weighted bipartite matching, and the minimum-spanning-tree problem.Subsequently, Driscoll, Gabow, Shrairman, and Tarjan [81] developed "relaxed heaps" as analternative to Fibonacci heaps.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
