chap21.htm

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

<h2>Decreasing a key</h2><P>
In the following pseudocode for the operation <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>, we assume as before that removing a node from a linked list does not change any of the structural fields in the removed node.<P>
<pre><a name="0881_16b7">FIB-HEAP-DECREASE-KEY(<I>H</I>,<I>x</I>,<I>k</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>k</I> &gt; <I>key</I>[<I>x</I>]</sub></sup></pre><P>
<pre>2     <B>then error</B> &quot;new key is greater than current key&quot;</sub></sup></pre><P>
<pre>3  <I>key</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>k</I></sub></sup></pre><P>
<pre>4  <I>y</I> <img src="../images/arrlt12.gif"> <I>p</I>[<I>x</I>]</sub></sup></pre><P>
<pre>5  <B>if</B> <I>y</I> <img src="../images/noteq.gif"> NIL and <I>key</I>[<I>x</I>] &lt; <I>key</I>[<I>y</I>]</sub></sup></pre><P>
<pre>6     <B>then</B> CUT(<I>H</I>,<I>x</I>,<I>y</I>)</sub></sup></pre><P>
<pre>7           CASCADING-CUT(<I>H</I>,<I>y</I>)</sub></sup></pre><P>
<pre>8  <B>if</B> <I>key</I>[<I>x</I>] &lt; <I>key</I>[<I>min</I>[<I>H</I>]]</sub></sup></pre><P>
<pre>9     <B>then</B> <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="0881_16b8">CUT(<I>H</I>,<I>x</I>,<I>y</I>)</sub></sup></pre><P>
<pre>1  remove <I>x</I> from the child list of <I>y</I>, decrementing <I>degree</I>[<I>y</I>]</sub></sup></pre><P>
<pre>2  add <I>x</I> to the root list of <I>H</I></sub></sup></pre><P>
<pre>3  <I>p</I>[<I>x</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>4  <I>mark</I>[<I>x</I>] <img src="../images/arrlt12.gif"> FALSE</sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="0881_16b9">CASCADING-CUT(<I>H</I>,<I>y</I>)</sub></sup></pre><P>
<pre>1  <I>z</I> <img src="../images/arrlt12.gif"> <I>p</I>[<I>y</I>]</sub></sup></pre><P>
<pre>2  <B>if</B> <I>z</I> <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>3     <B>then if</B> <I>mark</I>[<I>y</I>] = FALSE</sub></sup></pre><P>
<pre>4             <B>then</B> <I>mark</I>[<I>y</I>] <img src="../images/arrlt12.gif"> TRUE</sub></sup></pre><P>
<pre>5             <B>else</B> CUT(<I>H</I>,<I>y</I>,<I>z</I>)</sub></sup></pre><P>
<pre>6                  CASCADING-CUT(<I>H</I>,<I>z</I>)</sub></sup></pre><P>
The <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> procedure works as follows. Lines 1-3 ensure that the new key is no greater than the current key of <I>x</I> and then assign the new key to <I>x</I>. If <I>x</I> is a root or if <I>key</I>[<I>x</I>] <img src="../images/gteq.gif"> <I>key</I>[<I>y</I>], where <I>y</I> is <I>x</I>'s parent, then no structural changes need occur, since heap order has not been violated. Lines 4-5 test for this condition.<P>
<a name="0881_16ba">If heap order has been violated, many changes may occur. We start by <I><B>cutting</I></B> <I>x</I> in line 6. The <FONT FACE="Courier New" SIZE=2>CUT</FONT> procedure "cuts" the link between <I>x</I> and its parent <I>y</I>, making <I>x</I> a root.<P>
<a name="0881_16bb">We use the <I>mark</I> fields to obtain the desired time bounds. They help to produce the following effect. Suppose that <I>x</I> is a node that has undergone the following history:<P>
1.     at some time, <I>x</I> was a root,<P>
2.     then <I>x</I> was linked to another node,<P>
3.     then two children of <I>x</I> were removed by cuts.<P>
As soon as the second child has been lost, <I>x</I> is cut from its parent, making it a new root. The field <I>mark</I>[<I>x</I>] is <FONT FACE="Courier New" SIZE=2>TRUE</FONT> if steps 1 and 2 have occurred and one child of <I>x</I> has been cut. The <FONT FACE="Courier New" SIZE=2>CUT</FONT> procedure, therefore, clears <I>mark</I>[<I>x</I>] in line 4, since it performs step 1. (We can now see why line 3 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> clears <I>mark</I>[<I>y</I>]: node <I>y</I> is being linked to another node, and so step 2 is being performed. The next time a child of <I>y</I> is cut, <I>mark</I>[<I>y</I>] will be set to <FONT FACE="Courier New" SIZE=2>TRUE</FONT>.)<P>
<a name="0881_16bc"><a name="0881_16bd">We are not yet done, because <I>x</I> might be the second child cut from its parent <I>y</I> since the time that <I>y</I> was linked to another node. Therefore, line 7 of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> performs a <I><B>cascading-cut</I></B> operation on <I>y</I>. If <I>y</I> is a root, then the test in line 2 of <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> causes the procedure to just return. If <I>y</I> is unmarked, the procedure marks it in line 4, since its first child has just been cut, and returns. If <I>y</I> is marked, however, it has just lost its second child; <I>y</I> is cut in line 5, and <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> calls itself recursively in line 6 on y's parent <I>z</I>. The <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> procedure recurses its way up the tree until either a root or an unmarked node is found.<P>
Once all the cascading cuts have occurred, lines 8-9 of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> finish up by updating <I>min</I>[<I>H</I>] if necessary.<P>
Figure 21.4 shows the execution of two calls of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>, starting with the Fibonacci heap shown in Figure 21.4(a). The first call, shown in Figure 21.4(b), involves no cascading cuts. The second call, shown in Figures 21.4(c)-(e), invokes two cascading cuts.<P>
<a name="0881_16be">We shall now show that the amortized cost of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> is only <I>O</I>(1). We start by determining its actual cost. The <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> procedure takes <I>O</I>(1) time, plus the time to perform the cascading cuts. Suppose that <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> is recursively called <I>c</I> times from a given invocation of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>. Each call of <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> takes <I>O</I>(1) time exclusive of recursive calls. Thus, the actual cost of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY,</FONT> including all recursive calls, is <I>O</I>(<I>c</I>).<P>
<a name="0881_16bf">We next compute the change in potential. 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>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> operation. Each recursive call of <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT>, except for the last one, cuts a marked node and clears the mark bit. Afterward, there are <I>t</I>(<I>H</I>) + <I>c</I> trees (the original <I>t</I>(<I>H</I>) trees, <I>c</I>- 1 trees produced by cascading cuts, and the tree rooted at <I>x</I>) and at most <I>m</I>(<I>H</I>) - <I>c</I> + 2 marked nodes (<I>c</I> - 1 were unmarked by cascading cuts and the last call of <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> may have marked a node). The change in potential is therefore at most<P>
<pre>((<I>t</I>(<I>H</I>) + <I>c</I>) + 2(<I>m</I>(<I>H</I>) - <I>c</I> + 2)) - (<I>t</I>(<I>H</I>) + 2<I>m</I>(<I>H</I>)) = 4 - <I>c</I> .</sub></sup></pre><P>
Thus, the amortized cost of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> is at most<P>
<pre><I>O</I>(<I>c</I>) + 4 - <I>c</I> = <I>O</I>(1) ,</sub></sup></pre><P>
since we can scale up the units of potential to dominate the constant hidden in <I>O</I>(<I>c</I>).<P>
You can now see why the potential function was defined to include a term that is twice the number of marked nodes. When a marked node <I>y</I> is cut by a cascading cut, its mark bit is cleared, so the potential is reduced by 2. One unit of potential pays for the cut and the clearing of the mark bit, and the other unit compensates for the unit increase in potential due to node <I>y</I> becoming a root.<P>
<img src="434_a.gif"><P>
<h4><a name="0881_16c0">Figure 21.4 Two calls 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>DECREASE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>KEY</FONT></FONT></FONT></FONT></FONT></FONT></FONT>. (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 with key 35 has its key decreased to 5. In part (c), the node, now with key 5, becomes a root. Its parent, with key 26, is marked, so a cascading cut occurs. The node with key 26 is cut from its parent and made an unmarked root in (d). Another cascading cut occurs, since the node with key 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 this node were not a root, the cascading cuts would stop, since it is unmarked.) The result of the <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>DECREASE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>KEY</FONT></FONT></FONT></FONT></FONT></FONT></FONT> operation is shown in part (e), with min[H] pointing to the new minimum node.<a name="0881_16c0"></sub></sup></h4><P>
<P>







<h2>Deleting a node</h2><P>
<a name="0882_16c0"><a name="0882_16c1">It is easy to delete a node from an <I>n</I>-node Fibonacci heap in <I>O</I>(<I>D</I>(<I>n</I>)) amortized time, as is done by the following pseudocode. We assume that there is no key value of -<FONT FACE="Times New Roman" SIZE=3><img src="../images/infin.gif"></FONT> currently in the Fibonacci heap.<P>
<pre><a name="0882_16c2">FIB-HEAP-DELETE(<I>H, x</I>)</sub></sup></pre><P>
<pre>1  FIB-HEAP-DECREASE-KEY(<I>H</I>,<I> x</I>, -<img src="../images/infin.gif">)</sub></sup></pre><P>
<pre>2  FIB-HEAP-EXTRACT-MIN(<I>H</I>)</sub></sup></pre><P>
<FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> is analogous to <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. It makes <I>x </I>become the minimum node in the Fibonacci heap by giving it a uniquely small key of -<img src="../images/infin.gif">. Node <I>x</I> is then removed from the Fibonacci heap by 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> procedure. The amortized time of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> is the sum of the <I>O</I>(1) amortized time of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> and the <I>O</I>(<I>D</I>(<I>n</I>)) amortized time 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>.<P>
<P>







<h2><a name="0883_16c6">Exercises<a name="0883_16c6"></h2><P>
<a name="0883_16c7">21.3-1<a name="0883_16c7"><P>
<a name="0883_16c3"><a name="0883_16c4">Suppose that a root <I>x</I> in a Fibonacci heap is marked. Explain how <I>x</I> came to be a marked root. Argue that it doesn't matter to the analysis that <I>x</I> is marked, even though it is not a root that was first linked to another node and then lost one child.<P>
<a name="0883_16c8">21.3-2<a name="0883_16c8"><P>
<a name="0883_16c5">Justify the <I>O</I>(1) amortized time of <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> using the aggregate method of Section 18.1.<P>
<P>