Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 93
Текст из файла (страница 93)
. . , Uk-1 insome order.Thus, if an n-node Fibonacci heap is a collection of unordered binomial trees, then D(n) = lgn.The key idea in the mergeable-heap operations on Fibonacci heaps is to delay work as long aspossible. There is a performance trade-off among implementations of the various operations.If the number of trees in a Fibonacci heap is small, then during an EXTRACT-MIN operationwe can quickly determine which of the remaining nodes becomes the new minimum node.However, as we saw with binomial heaps in Exercise 19.2-10, we pay a price for ensuring thatthe number of trees is small: it can take up to Ω(lg n) time to insert a node into a binomialheap or to unite two binomial heaps. As we shall see, we do not attempt to consolidate trees ina Fibonacci heap when we insert a new node or unite two heaps.
We save the consolidationfor the EXTRACT-MIN operation, which is when we really need to find the new minimumnode.Creating a new Fibonacci heapTo make an empty Fibonacci heap, the MAKE-FIB-HEAP procedure allocates and returns theFibonacci heap object H , where n[H ] = 0 and min[H ] = NIL; there are no trees in H .Because t(H) = 0 and m(H) = 0, the potential of the empty Fibonacci heap is Φ(H) = 0. Theamortized cost of MAKE-FIB-HEAP is thus equal to its O(1) actual cost.Inserting a nodeThe following procedure inserts node x into Fibonacci heap H , assuming that the node hasalready been allocated and that key[x] has already been filled in.FIB-HEAP-INSERT(H, x)1 degree[x] ← 02 p[x] ← NIL3 child[x] ← NIL4 left[x] ← x5 right[x] ← x6 mark[x] ← FALSE7 concatenate the root list containing x with root list H8 if min[H] = NIL or key[x] < key[min[H]]9then min[H] ← x10 n[H] ← n[H] + 1After lines 1-6 initialize the structural fields of node x, making it its own circular, doublylinked list, line 7 adds x to the root list of H in O(1) actual time.
Thus, node x becomes asingle-node min-heap-ordered tree, and thus an unordered binomial tree, in the Fibonacciheap. It has no children and is unmarked. Lines 8-9 then update the pointer to the minimumnode of Fibonacci heap H if necessary. Finally, line 10 increments n[H] to reflect the additionof the new node.
Figure 20.2 shows a node with key 21 inserted into the Fibonacci heap ofFigure 20.1.Figure 20.2: Inserting a node into a Fibonacci heap. (a) A Fibonacci heap H. (b) Fibonacciheap H after the node with key 21 has been inserted. The node becomes its own min-heapordered tree and is then added to the root list, becoming the left sibling of the root.Unlike the BINOMIAL-HEAP-INSERT procedure, FIB-HEAP-INSERT makes no attempt toconsolidate the trees within the Fibonacci heap. If k consecutive FIB-HEAP-INSERToperations occur, then k single-node trees are added to the root list.To determine the amortized cost of FIB-HEAP-INSERT, let H be the input Fibonacci heapand H′ be the resulting Fibonacci heap.
Then, t(H′) = t(H)+1 and m(H′) = m(H), and theincrease in potential is((t(H) + 1) + 2 m(H)) - (t(H) + 2 m(H)) = 1.Since the actual cost is O(1), the amortized cost is O(1) + 1 = O(1).Finding the minimum nodeThe minimum node of a Fibonacci heap H is given by the pointer min[H ], so we can find theminimum node in O(1) actual time. Because the potential of H does not change, the amortizedcost of this operation is equal to its O(1) actual cost.Uniting two Fibonacci heapsThe following procedure unites Fibonacci heaps H1 and H2, destroying H1 and H2 in theprocess. It simply concatenates the root lists of H1 and H2 and then determines the newminimum node.FIB-HEAP-UNION(H1, H2)1 H ← MAKE-FIB-HEAP()2 min[H] ← min[H1]3 concatenate the root list of H2 with the root list of H4 if (min[H1] = NIL) or (min[H2] ≠ NIL and min[H2] < min[H1])5then min[H] ← min[H2]6 n[H] ← n[H1] + n[H2]7 free the objects H1 and H28 return HLines 1-3 concatenate the root lists of H1 and H2 into a new root list H.
Lines 2, 4, and 5 setthe minimum node of H , and line 6 sets n[H] to the total number of nodes. The Fibonacciheap objects H1 and H2 are freed in line 7, and line 8 returns the resulting Fibonacci heap H.As in the FIB-HEAP-INSERT procedure, no consolidation of trees occurs.The change in potential isΦ(H) - (Φ(H1) + Φ(H2))= (t(H) + 2m(H)) - ((t(H1) + 2 m(H1)) + (t(H2) + 2 m(H2)))= 0,because t(H) = t(H1) + t(H2) and m(H) = m(H1) + m(H2). The amortized cost of FIB-HEAPUNION is therefore equal to its O(1) actual cost.Extracting the minimum nodeThe process of extracting the minimum node is the most complicated of the operationspresented in this section. It is also where the delayed work of consolidating trees in the rootlist finally occurs. The following pseudocode extracts the minimum node.
The code assumesfor convenience that when a node is removed from a linked list, pointers remaining in the listare updated, but pointers in the extracted node are left unchanged. It also uses the auxiliaryprocedure CONSOLIDATE, which will be presented shortly.FIB-HEAP-EXTRACT-MIN(H)1 z ← min[H]2 if z ≠ NIL3then for each child x of z4do add x to the root list of H5p[x] ← NIL6remove z from the root list of H7if z = right[z]8then min[H] ← NIL9else min[H] ← right[z]10CONSOLIDATE(H)11n[H] ← n[H] - 112 return zAs shown in Figure 20.3, FIB-HEAP-EXTRACT-MIN works by first making a root out ofeach of the minimum node's children and removing the minimum node from the root list. Itthen consolidates the root list by linking roots of equal degree until at most one root remainsof each degree.Figure 20.3: The action of FIB-HEAP-EXTRACT-MIN.
(a) A Fibonacci heap H. (b) Thesituation after the minimum node z is removed from the root list and its children are added tothe root list. (c)-(e) The array A and the trees after each of the first three iterations of the forloop of lines 3-13 of the procedure CONSOLIDATE. The root list is processed by starting atthe node pointed to by min[H ] and following right pointers. Each part shows the values of wand x at the end of an iteration. (f)-(h) The next iteration of the for loop, with the values of wand x shown at the end of each iteration of the while loop of lines 6-12. Part (f) shows thesituation after the first time through the while loop.
The node with key 23 has been linked tothe node with key 7, which is now pointed to by x. In part (g), the node with key 17 has beenlinked to the node with key 7, which is still pointed to by x. In part (h), the node with key 24has been linked to the node with key 7. Since no node was previously pointed to by A[3], atthe end of the for loop iteration, A[3] is set to point to the root of the resulting tree.
(i)-(l) Thesituation after each of the next four iterations of the for loop. (m) Fibonacci heap H afterreconstruction of the root list from the array A and determination of the new min[H] pointer.We start in line 1 by saving a pointer z to the minimum node; this pointer is returned at theend. If z = NIL, then Fibonacci heap H is already empty and we are done. Otherwise, as in theBINOMIAL-HEAP-EXTRACT-MIN procedure, we delete node z from H by making all of z'schildren roots of H in lines 3-5 (putting them into the root list) and removing z from the rootlist in line 6. If z = right[z] after line 6, then z was the only node on the root list and it had nochildren, so all that remains is to make the Fibonacci heap empty in line 8 before returning z.Otherwise, we set the pointer min[H] into the root list to point to a node other than z (in thiscase, right[z]), which is not necessarily going to be the new minimum node when FIB-HEAPEXTRACT-MIN is done.
Figure 20.3(b) shows the Fibonacci heap of Figure 20.3(a) after line9 has been performed.The next step, in which we reduce the number of trees in the Fibonacci heap, is consolidatingthe root list of H; this is performed by the call CONSOLIDATE(H). Consolidating the rootlist consists of repeatedly executing the following steps until every root in the root list has adistinct degree value.1. Find two roots x and y in the root list with the same degree, where key[x] ≤ key[y].2. Link y to x: remove y from the root list, and make y a child of x. This operation isperformed by the FIB-HEAP-LINK procedure.
The field degree[x] is incremented,and the mark on y, if any, is cleared.The procedure CONSOLIDATE uses an auxiliary array A[0currently a root with degree[y] = i.D(n[H])]; if A[i] = y, then y isCONSOLIDATE(H)1 for i ← 0 to D(n[H])2do A[i] ← NIL3 for each node w in the root list of H4do x ← w5d ← degree[x]6while A[d] ≠ NIL7do y ← A[d]▹ Another node with the same degree as x.8if key[x] > key[y]9then exchange x ↔ y10FIB-HEAP-LINK(H, y, x)11A[d] ← NIL12d ← d + 113A[d] ← x14 min[H] ← NIL15 for i ← 0 to D(n[H])16do if A[i] ≠ NIL17then add A[i] to the root list of H18if min[H] = NIL or key[A[i]] < key[min[H]]19then min[H] ← A[i]FIB-HEAP-LINK(H, y, x)1 remove y from the root list of H2 make y a child of x, incrementing degree[x]3 mark[y] ← FALSEIn detail, the CONSOLIDATE procedure works as follows.
Lines 1-2 initialize A by makingeach entry NIL. The for loop of lines 3-13 processes each root w in the root list. Afterprocessing each root w, it ends up in a tree rooted at some node x, which may or may not beidentical to w. Of the processed roots, no others will have the same degree as x, and so we willset array entry A[degree[x]] to point to x. When this for loop terminates, at most one root ofeach degree will remain, and the array A will point to each remaining root.The while loop of lines 6-12 repeatedly links the root x of the tree containing node w toanother tree whose root has the same degree as x, until no other root has the same degree.
Thiswhile loop maintains the following invariant:•At the start of each iteration of the while loop, d = degree[x].We use this loop invariant as follows:•••Initialization: Line 5 ensures that the loop invariant holds the first time we enter theloop.Maintenance: In each iteration of the while loop, A[d] points to some root y.
Becaused = degree[x] = degree[y], we want to link x and y. Whichever of x and y has thesmaller key becomes the parent of the other as a result of the link operation, and solines 8-9 exchange the pointers to x and y if necessary. Next, we link y to x by the callFIB-HEAP-LINK(H, y, x) in line 10. This call increments degree[x] but leavesdegree[y] as d. Because node y is no longer a root, the pointer to it in array A isremoved in line 11. Because the call of FIB-HEAP-LINK increments the value ofdegree[x], line 12 restores the invariant that d = degree[x].Termination: We repeat the while loop until A[d] = NIL, in which case there is noother root with the same degree as x.After the while loop terminates, we set A[d] to x in line 13 and perform the next iteration ofthe for loop.Figures 20.3(c)-(e) show the array A and the resulting trees after the first three iterations of thefor loop of lines 3-13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
