chap21.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<pre>9<B>              else</B> <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>right</I>[<I>z</I>]</sub></sup></pre><P>
<pre>10                   CONSOLIDATE(<I>H</I>)</sub></sup></pre><P>
<pre>11           <I>n</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>n</I>[<I>H</I>] - 1</sub></sup></pre><P>
<pre>12  <B>return </B><I>z</I></sub></sup></pre><P>
As shown in Figure 21.3, <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT-</FONT><FONT FACE="Courier New" SIZE=2>MIN</FONT> works by first making a root out of each of the minimum node's children and removing the minimum node from the root list. It then consolidates the root list by linking roots of equal degree until at most one root remains of each degree.<P>
We start in line 1 by saving a pointer <I>z</I> to the minimum node; this pointer is returned at the end. If <I>z</I> = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, then Fibonacci heap <I>H</I> is already empty and we are done. Otherwise, as in the <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> procedure, we delete node <I>z</I> from <I>H</I> by making all of <I>z</I>'s children roots of <I>H</I> in lines 3-5 (putting them into the root list) and removing <I>z </I>from the root list in line 6. If <I>z</I> = <I>right</I>[<I>z</I>] after line 6, then <I>z</I> was the only node on the root list and it had no children, so all that remains is to make the Fibonacci heap empty in line 8 before returning <I>z.</I> Otherwise, we set the pointer <I>min</I>[<I>H</I>] into the root list to point to a node other than <I>z</I> (in this case, <I>right</I>[<I>z</I>]). Figure 21.3(b) shows the Fibonacci heap of Figure 21.3(a) after line 9 has been performed.<P>
<a name="087e_16ab">The next step, in which we reduce the number of trees in the Fibonacci heap, is <I><B>consolidating</I></B> the root list of <I>H</I>; this is performed by the call <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT>(<I>H</I>). Consolidating the root list consists of repeatedly executing the following steps until every root in the root list has a distinct <I>degree</I> value.<P>
1.     Find two roots <I>x</I> and <I>y</I> in the root list with the same degree, where <I>key</I>[<I>x</I>] <img src="../images/lteq12.gif"> <I>key</I>[<I>y</I>].<P>
<a name="087e_16ac">2.     <I><B>Link</I></B> <I>y</I> to <I>x</I>: remove <I>y</I> from the root list, and make <I>y</I> a child of <I>x</I>. This operation is performed by the <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>LINK</FONT> procedure. The field <I>degree</I>[<I>x</I>] is incremented, and the mark on <I>y</I>, if any, is cleared.<P>
<a name="087e_16ad">The procedure <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT> uses an auxiliary array <I>A</I>[0 . . <I>D</I>(<I>n</I>[<I>H</I>])]; if <I>A</I>[<I>i</I>] = <I>y</I>, then <I>y</I> is currently a root with <I>degree</I>[<I>y</I>] = <I>i</I>.<P>
<pre>CONSOLIDATE(<I>H</I>)</sub></sup></pre><P>
<pre>1 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 0 <B>to</B> <I>D</I>(<I>n</I>[<I>H</I>])</sub></sup></pre><P>
<pre>2      <B>do</B> <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>3 <B>for</B> each node <I>w </I>in the root list of <I>H</I></sub></sup></pre><P>
<pre>4      <B>do</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>w</I></sub></sup></pre><P>
<pre>5         <I>d</I> <img src="../images/arrlt12.gif"> <I>degree</I>[<I>x</I>]</sub></sup></pre><P>
<pre>6         <B>while</B> <I>A</I>[<I>d</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>7            <B>do</B> <I>y</I> <img src="../images/arrlt12.gif"> <I>A</I>[<I>d</I>]</sub></sup></pre><P>
<pre>8               <B>if</B> <I>key</I>[<I>x</I>] &gt; <I>key</I>[<I>y</I>]</sub></sup></pre><P>
<pre>9                  <B>then</B> exchange <I>x</I> <img src="../images/dblarr12.gif"> <I>y</I></sub></sup></pre><P>
<pre>10                FIB-HEAP-LINK(<I>H</I>,<I>y</I>,<I>x</I>)</sub></sup></pre><P>
<pre>11                <I>A</I>[<I>d</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>12                <I>d</I> <img src="../images/arrlt12.gif"> <I>d </I>+ 1</sub></sup></pre><P>
<pre>13         <I>A</I>[<I>d</I>] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>14 <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>15 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 0 <B>to</B> <I>D</I>(<I>n</I>[<I>H</I>])</sub></sup></pre><P>
<pre>16      <B>do if</B> <I>A</I>[<I>i</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>17            <B>then</B> add <I>A</I>[<I>i</I>] to the root list of <I>H</I></sub></sup></pre><P>
<pre>18                 <B>if</B> <I>min</I>[<I>H</I>] = NIL or <I>key</I>[<I>A</I>[<I>i</I>]] &lt; <I>key</I>[<I>min</I>[<I>H</I>]]</sub></sup></pre><P>
<pre>19                    <B>then</B> <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>A</I>[<I>i</I>]</sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="087e_16ae">FIB-HEAP-LINK(<I>H, y, x</I>)</sub></sup></pre><P>
<pre>1  remove <I>y</I> from the root list of <I>H</I></sub></sup></pre><P>
<pre>2  make <I>y</I> a child of <I>x</I>, incrementing <I>degree</I>[<I>x</I>]</sub></sup></pre><P>
<pre>3  <I>mark</I>[<I>y</I>] <img src="../images/arrlt12.gif"> FALSE</sub></sup></pre><P>
In detail, the <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT> procedure works as follows. In lines 1-2, we initialize <I>A</I> by making each entry <FONT FACE="Courier New" SIZE=2>NIL</FONT>. When we are done processing each root <I>w</I>, it ends up in a tree rooted at some node <I>x</I>, which may or may not be identical to <I>w</I>. Array entry <I>A</I>[<I>degree</I>[<I>x</I>]] will then be set to point to <I>x</I>. In the <B>for</B> loop of lines 3-13, we examine each root <I>w</I> in the root list. The invariant maintained during each iteration of the <B>for</B> loop is that node <I>x</I> is the root of the tree containing node <I>w</I>. The <B>while</B> loop of lines 6-12 maintains the invariant that <I>d</I> = <I>degree</I>[<I>x</I>] (except in line 11, as we shall see in a moment). In each iteration of the <B>while</B> loop, <I>A</I>[<I>d</I>] points to some root <I>y</I>. Because <I>d</I> = <I>degree</I>[<I>x</I>] = <I>degree</I>[<I>y</I>], we want to link <I>x</I> and <I>y</I>. Whichever of <I>x</I> and <I>y</I> has the smaller key becomes the parent of the other as a result of the link operation, and so lines 8-9 exchange the pointers to <I>x</I> and <I>y</I> if necessary. Next, we link <I>y</I> to <I>x</I> by the call <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>LINK</FONT>(<I>H,y,x</I>) in line 10. This call increments <I>degree</I>[<I>x</I>] but leaves <I>degree</I>[<I>y</I>] as <I>d</I>. Because node <I>y</I> is no longer a root, the pointer to it in array <I>A</I> is removed in line 11. Because the value of <I>degree</I>[<I>x</I>] is incremented by the call of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>LINK</FONT>, line 12 restores the invariant that <I>d</I> = <I>degree</I>[<I>x</I>]. We repeat the <B>while</B> loop until <I>A</I>[<I>d</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, in which case there is no other root with the same degree as <I>x</I>. We set <I>A</I>[<I>d</I>] to <I>x</I> in line 13 and perform the next iteration of the <B>for</B> loop. Figures 21.3(c)-(e) show the array <I>A</I> and the resulting trees after the first three iterations of the <B>for</B> loop of lines 3-13. In the next iteration of the <B>for</B> loop, three links occur; their results are shown in Figures 21.3(f)-(h). Figures 21.3(i)-(1) show the result of the next four iterations of the <B>for</B> loop.<P>
<img src="428_a.gif"><P>
<h4><a name="087e_16b1">Figure 21.3 The action of <FONT FACE="Courier New" SIZE=2>FIB<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>HEAP<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>EXTRACT<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>MIN</FONT></FONT></FONT></FONT></FONT></FONT></FONT>. (a) A Fibonacci heap H. (b) The situation after the minimum node z is removed from the root list and its children are added to the root list. (c)-(e) The array A and the trees after each of the first three iterations of the for loop of lines 3-13 of the procedure <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT>. The root list is processed by starting at the minimum node and following right pointers. Each part shows the values of w and x at the end of an iteration. (f)-(h) The next iteration of the for loop, with the values of w and x shown at the end of each iteration of the while loop of lines 6-12. Part (f) shows the situation after the first time through the while loop. The node with key 23 has been linked to the node with key 7, which is now pointed to by x. In part (g), the node with key 17 has been linked to the node with key 7, which is still pointed to by x. In part (h), the node with key 24 has been linked to the node with key 7. Since no node was previously pointed to by A[3], at the end of the for loop iteration, A[3] is set to point to the root of the resulting tree. (i)-(l) The situation after each of the next four iterations of the while loop. (m) Fibonacci heap H after reconstruction of the root list from the array A and determination of the new min[H] pointer.<a name="087e_16b1"></sub></sup></h4><P>
<img src="429_a.gif"><P>
All that remains is to clean up. Once the <B>for</B> loop of lines 3-13 completes, line 14 empties the root list, and lines 15-19 reconstruct it. The resulting Fibonacci heap is shown in Figure 21.3(m). After consolidating the root list, <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> finishes up by decrementing <I>n</I>[<I>H</I>] in line 11 and returning a pointer to the deleted node <I>z</I> in line 12.<P>
Observe that if all trees in the Fibonacci heap are unordered binomial trees before <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> is executed, then they are all unordered binomial trees afterward. There are two ways in which trees are changed. First, in lines 3-5 of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT>, each child <I>x</I> of root <I>z</I> becomes a root. By Exercise 21.2-2, each new tree is itself an unordered binomial tree. Second, trees are linked by <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>LINK</FONT> only if they have the same degree. Since all trees are unordered binomial trees before the link occurs, two trees whose roots each have <I>k</I> children must have the structure of <I>U<SUB>k</I></SUB>. The resulting tree therefore has the structure of <I>U<SUB>k</I>+1</SUB>.<P>
<a name="087e_16af">We are now ready to show that the amortized cost of extracting the minimum node of an <I>n</I>-node Fibonacci heap is <I>O</I>(<I>D</I>(<I>n</I>)). Let <I>H</I> denote the Fibonacci heap just prior to the <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> operation.<P>
The actual cost of extracting the minimum node can be accounted for as follows. An <I>O(D(n))</I> contribution comes from there being at most <I>D</I>(<I>n</I>) children of the minimum node that are processed in <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> and from the work in lines 1-2 and 14-19 of <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT>. It remains to analyze the contribution from the <B>for</B> loop of lines 3-13. The size of the root list upon calling <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT> is at most <I>D</I>(<I>n</I>) + <I>t</I>(<I>H</I>) - 1, since it consists of the original <I>t</I>(<I>H</I>) root-list nodes, minus the extracted root node, plus the children of the extracted node, which number at most <I>D</I>(<I>n</I>). Every time through the <B>while</B> loop of lines 6-12, one of the roots is linked to another, and thus the total amount of work performed in the <B>for </B>loop is at most proportional to <I>D</I>(<I>n</I>) + <I>t</I>(<I>H</I>). Thus, the total actual work is <I>O</I>(<I>D</I>(<I>n</I>) <I>+ t</I>(<I>H</I>)).<P>
<a name="087e_16b0">The potential before extracting the minimum node is <I>t</I>(<I>H</I>) + 2<I>m</I>(<I>H</I>), and the potential afterward is at most (<I>D</I>(<I>n</I>) + 1) + 2<I>m</I>(<I>H</I>), since at most <I>D</I>(<I>n</I>) + 1 roots remain and no nodes become marked during the operation. The amortized cost is thus at most<P>
<pre><I>O</I>(<I>D</I>(<I>n</I>) + <I>t</I>(<I>H</I>)) + ((<I>D</I>(<I>n</I>) + 1) + 2<I>m</I>(<I>H</I>)) - (<I>t</I>(<I>H</I>) + 2<I>m</I>(<I>H</I>))</sub></sup></pre><P>
<pre>= <I>O</I>(<I>D</I>(<I>n</I>)) + <I>O</I>(<I>t</I>(<I>H</I>)) - <I>t</I>(<I>H</I>)</sub></sup></pre><P>
<pre>= <I>O</I>(<I>D</I>(<I>n</I>)),</sub></sup></pre><P>
since we can scale up the units of potential to dominate the constant hidden in <I>O</I>(<I>t</I>(<I>H</I>)). Intuitively, the cost of performing each link is paid for by the reduction in potential due to the link reducing the number of roots by one.<P>
<P>







<h2><a name="087f_16b5">Exercises<a name="087f_16b5"></h2><P>
<a name="087f_16b6">21.2-1<a name="087f_16b6"><P>
Show the Fibonacci heap that results from calling <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> on the Fibonacci heap shown in Figure 21.3(m).<P>
<a name="087f_16b7">21.2-2<a name="087f_16b7"><P>
Prove that Lemma 20.1 holds for unordered binomial trees, but with property 4' in place of property 4.<P>
<a name="087f_16b8">21.2-3<a name="087f_16b8"><P>
<a name="087f_16b1"><a name="087f_16b2">Show that if only the mergeable-heap operations are supported, the maximum degree <I>D(n)</I> in an <I>n</I>-node Fibonacci heap is at most <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>.<P>
<a name="087f_16b9">21.2-4<a name="087f_16b9"><P>
<a name="087f_16b3">Professor McGee has devised a new data structure based on Fibonacci heaps. A McGee heap has the same structure as a Fibonacci heap and supports the mergeable-heap operations. The implementations of the operations are the same as for Fibonacci heaps, except that insertion and union perform consolidation as their last step. What are the worst-case running time of operations on McGee heaps? How novel is the professor's data structure?<P>
<a name="087f_16ba">21.2-5<a name="087f_16ba"><P>
<a name="087f_16b4">Argue that when the only operations on keys are comparing two keys (as is the case for all the implementations in this chapter), not all of the mergeable-heap operations can run in <I>O</I>(1) amortized time.<P>
<P>


<P>







<h1><a name="0880_16b7">21.3 Decreasing a key and deleting a node<a name="0880_16b7"></h1><P>
<a name="0880_16b5"><a name="0880_16b6">In this section, we show how to decrease the key of a node in a Fibonacci heap in <I>O</I>(1) amortized time and how to delete any node from an <I>n</I>-node Fibonacci heap in <I>O</I>(<I>D</I>(<I>n</I>)) 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 <I>D</I>(<I>n</I>) by <I>O</I>(1g <I>n</I>). Proving this bound will imply that <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> and <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> run in <I>O</I>(1g <I>n</I>) amortized time.<P>