chap21.htm

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

<P>







<h1><a name="0884_16cb">21.4 Bounding the maximum degree<a name="0884_16cb"></h1><P>
<a name="0884_16c6"><a name="0884_16c7"><a name="0884_16c8">To prove that 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>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> is <I>O</I>(l<I>g n</I>), we must show that the upper bound <I>D</I>(<I>n</I>) on the degree of any node of an <I>n</I>-node Fibonacci heap is <I>O</I>(lg <I>n</I>). By Exercise 21.2-3, when all trees in the Fibonacci heap are unordered binomial trees, <I>D(n)</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg <I>n</I><img src="../images/hfbrdr12.gif">. The cuts that occur in <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>, however, may cause trees within the Fibonacci heap to violate the unordered binomial tree properties. In this section, we shall show that because we cut a node from its parent as soon as it loses two children, <I>D</I>(<I>n</I>) is <I>O</I>(lg <I>n</I>). In particular, we shall show that <I>D</I>(<I>n</I>) <img src="../images/lteq12.gif"> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>log<img src="../images/phicap12.gif"><SUB> <I>n</SUB></I><img src="../images/hfbrdr12.gif">, where <img src="435_a.gif">.<P>
The key to the analysis is as follows. For each node <I>x</I> within a Fibonacci heap, define size(<I>x</I>) to be the number of nodes, including <I>x</I> itself, in the subtree rooted at <I>x</I>. (Note that <I>x</I> need not be in the root list--it can be any node at all.) We shall show that size(<I>x</I>) is exponential in <I>degree</I>[<I>x</I>]. Bear in mind that <I>degree</I>[<I>x</I>] is always maintained as an accurate count of the degree of <I>x</I>.<P>
<a name="0884_16cc">Lemma 21.1<a name="0884_16cc"><P>
Let <I>x</I> be any node in a Fibonacci heap, and suppose that <I>degree</I>[<I>x</I>]<I> = k. </I>Let <I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB>, ..., <I>y<SUB>k</I></SUB> denote the children of <I>x</I> in the order in which they were linked to <I>x</I>, from the earliest to the latest. Then, <I>degree</I> [<I>y</I><SUB>1</SUB>] <img src="../images/gteq.gif"> 0 and <I>degree</I>[<I>y<SUB>i</I></SUB>] <img src="../images/gteq.gif"> <I>i</I> - 2 for <I>i</I> = 2, 3, . . . , <I>k</I>.<P>
<I><B>Proof     </I></B>Obviously, <I>degree</I>[<I>y</I><SUB>1</SUB>] <img src="../images/gteq.gif"> 0.<P>
For <I>i</I> <img src="../images/gteq.gif"> 2, we note that when <I>y<SUB>i</I></SUB> was linked to <I>x</I>, all of <I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB>, . . . , <I>y<SUB>i</I></SUB>-<I>1</I><SUB> </SUB>were children of <I>x</I>, so we must have had <I>degree</I>[<I>x</I>] <img src="../images/gteq.gif"> i - 1. Node <I>y<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB> is linked to <I>x</I> only if <I>degree</I>[<I>x</I>] = <I>degree</I>[<I>y<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB>], so we must have also had <I>degree</I>[<I>y<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB>] <img src="../images/gteq.gif"> <I>i</I> - 1 at that time. Since then, node <I>y<SUB>i</I></SUB> has lost at most one child, since it would have been cut from <I>x</I> if it had lost two children. We conclude that <I>degree</I> [<I>y<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB> ] <img src="../images/gteq.gif"> <I>i</I> - 2.      <P>
<a name="0884_16ca">We finally come to the part of the analysis that explains the name &quot;Fibonacci heaps.&quot; Recall from Section 2.2 that for <I>k</I> = 0, 1, 2, . . . , the <I>k</I>th Fibonacci number is defined by the recurrence<P>
<img src="436_a.gif"><P>
The following lemma gives another way to express <I>F<SUB>k</I></SUB>.<P>
<a name="0884_16cd">Lemma 21.2<a name="0884_16cd"><P>
For all integers <I>k</I> <img src="../images/gteq.gif"> 0,<P>
<img src="436_b.gif"><P>
<I><B>Proof     </I></B>The proof is by induction on <I>k</I>. When <I>k</I> = 0,<P>
<img src="436_c.gif"><P>
We now assume the inductive hypothesis that <img src="436_d.gif">, and we have<P>
<img src="436_e.gif"><P>
The following lemma and its corollary complete the analysis. It uses the inequality (proved in Exercise 2.2-8)<P>
<pre><I>F<SUB>k</I>+2</SUB> <img src="../images/gteq.gif"> <img src="../images/phicap12.gif"><SUP>k <I></SUP>,</I></sub></sup></pre><P>
where <img src="../images/phicap12.gif"><I></I> is the golden ratio defined in equation (2.14) as <img src="436_f.gif">.<P>
<a name="0884_16ce">Lemma 21.3<a name="0884_16ce"><P>
Let <I>x </I>be any node in a Fibonacci heap, and let <I>k</I> = <I>degree</I>[<I>x</I>]. Then, size (<I>x</I>) <img src="../images/gteq.gif"> <I>F<SUB>k</I>+2</SUB> <img src="../images/gteq.gif"> <img src="../images/phicap12.gif"><SUP>k<I></SUP>, where <img src="../images/phicap12.gif"></I> = <img src="437_a.gif">.<P>
<I><B>Proof     </I></B>Let <I>s<SUB>k</I></SUB> denote the minimum possible value of size(<I>z</I>) over all nodes <I>z</I> such that <I>degree</I>[<I>z</I>] = <I>k</I>. Trivially, <I>s</I><SUB>0</SUB> = 1, <I>s</I><SUB>1</SUB> = 2, and <I>s</I><SUB>2</SUB> = 3. The number <I>s<SUB>k</I></SUB> is at most size(<I>x</I>). As in Lemma 21.1, let <I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB>, . . . , <I>y<SUB>k</I></SUB> denote the children of<I> x</I> in the order in which they were linked to <I>x</I>. To compute a lower bound on size(<I>x</I>), we count one for <I>x</I> itself and one for the first child <I>y</I><SUB>1</SUB> (for which size(<I>y</I><SUB>1</SUB>) <img src="../images/gteq.gif"> 1 ) and then apply Lemma 21.1 for the other children. We thus have<P>
<img src="437_b.gif"><P>
We now show by induction on <I>k</I> that <I>s<SUB>k</I></SUB> <img src="../images/gteq.gif"> <I>F<SUB>k</I>+2</SUB> for all nonnegative integer <I>k</I>. The bases, for <I>k</I> = 0 and <I>k</I> = 1, are trivial. For the inductive step, we assume that <I>k</I> <img src="../images/gteq.gif"> 2 and that <I>s<SUB>i</I></SUB> <img src="../images/gteq.gif"> <I>F<SUB>i </I>+ 2</SUB> for <I>i</I> = 0, 1, . . . , <I>k</I> - 1. We have<P>
<img src="437_c.gif"><P>
The last equality follows from Lemma 21.2.<P>
Thus, we have shown that size(<I>x</I>) <img src="../images/gteq.gif"> <I>s<SUB>k </I>+ 2</SUB> <img src="../images/gteq.gif"> <img src="../images/phicap12.gif"><SUP>k<I></SUP>.      </I><P>
<a name="0884_16cf">Corollary 21.4<a name="0884_16cf"><P>
The maximum degree <I>D</I>(<I>n</I>) of any node in an <I>n</I>-node Fibonacci heap is <I>O</I>(lg <I>n</I>).<P>
<I><B>Proof     </I></B>Let <I>x</I> be any node in an <I>n</I>-node Fibonacci heap, and let <I>k</I> =<I> degree</I>[<I>x</I>]. By Lemma 21.3, we have <I>n</I> <img src="../images/gteq.gif"><I> size(</I>x<I>) <img src="../images/gteq.gif"> <img src="../images/phicap12.gif"><SUP>k</I></SUP>. Taking base-<img src="../images/phicap12.gif"><I></I> logarithms yields <I>k</I> <img src="../images/gteq.gif"> log<img src="../images/phicap12.gif"><I><SUB> </I>n<I></SUB>. (In fact, because </I>k<I> is an integer, </I>k<I> <img src="../images/lteq12.gif"></I> <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>log<I><SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/phicap12.gif"><I></I></FONT><SUB> <I>n<FONT FACE="Times New Roman" SIZE=2></SUB></I><img src="../images/hfbrdr12.gif"><I>.</I></FONT>) The maximum degree <I>D</I>(<I>n</I>) of any node is thus <I>O</I>(lg <I>n</I>).      <P>





<h2><a name="0885_16cd">Exercises<a name="0885_16cd"></h2><P>
<a name="0885_16ce">21.4-1<a name="0885_16ce"><P>
<a name="0885_16cb">Professor Pinocchio claims that the height of an <I>n</I>-node Fibonacci heap is <I>O</I>(lg <I>n</I>). Show that the professor is mistaken by exhibiting, for any positive integer <I>n</I>, a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of <I>n</I> nodes.<P>
<a name="0885_16cf">21.4-2<a name="0885_16cf"><P>
<a name="0885_16cc">Suppose we generalize the cascading-cut rule to cut a node <I>x</I> from its parent as soon as it loses its <I>k</I>th child, for some integer constant <I>k</I>. (The rule in Section 21.3 uses <I>k</I> = 2.) For what values of <I>k</I> is <I>D</I>(<I>n</I>) = <I>O</I>(lg <I>n</I>)?<P>
<P>


<P>







<h1><a name="0886_16d6">Problems<a name="0886_16d6"></h1><P>
<a name="0886_16d7">21-1 Alternative implementation of deletion<a name="0886_16d7"><P>
<a name="0886_16cd"><a name="0886_16ce"><a name="0886_16cf">Professor Pisano has proposed the following variant of the <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> procedure, claiming that it runs faster when the node being deleted is not the node pointed to by <I>min</I>[<I>H</I>].<P>
<pre>PISANO-DELETE(<I>H, x</I>)</sub></sup></pre><P>
<pre>1<B>  if</B> <I>x</I> = <I>min</I>[<I>H</I>]</sub></sup></pre><P>
<pre>2<B>     then</B> FIB-HEAP-EXTRACT-MIN(<I>H</I>)</sub></sup></pre><P>
<pre>3<B>     else</B> <I>y</I> <img src="../images/arrlt12.gif"> <I>p</I>[<I>x</I>]</sub></sup></pre><P>
<pre>4<B>          if</B> <I>y</I> <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>5<B>             then</B> CUT(<I>H,x,y</I>)</sub></sup></pre><P>
<pre>6                  CASCADING-CUT(<I>H,y</I>)</sub></sup></pre><P>
<pre>7          add <I>x</I>'s child list to the root list of <I>H</I></sub></sup></pre><P>
<pre>8          remove <I>x</I> from the root list of <I>H</I></sub></sup></pre><P>
<I><B>a.</I></B>     The professor's claim that this procedure runs faster is based partly on the assumption that line 7 can be performed in <I>O</I>(1) actual time. What is wrong with this assumption?<P>
<I><B>b.</I></B>     Give a good upper bound on the actual time of <FONT FACE="Courier New" SIZE=2>PISANO</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> when <I>x</I> <img src="../images/noteq.gif"> <I>min</I>[<I>H</I>]. Your bound should be in terms of <I>degree</I>[<I>x</I>] and the number <I>c</I> of calls to the <FONT FACE="Courier New" SIZE=2>CASCADING</FONT>-<FONT FACE="Courier New" SIZE=2>CUT</FONT> procedure.<P>
<I><B>c.</I></B>     Let <I>H'</I> be the Fibonacci heap that results from an execution of <FONT FACE="Courier New" SIZE=2>PISANO</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>(<I>H, x</I>). Assuming that node <I>x</I> is not a root, bound the potential of <I>H'</I> in terms of <I>degree</I>[<I>x</I>], <I>c, t</I>(<I>H</I>), and <I>m</I>(<I>H</I>).<P>
<I><B>d.</I>     </B>Conclude that the amortized time for <FONT FACE="Courier New" SIZE=2>PISANO</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> is asymptotically no better than for <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>, even when <I>x</I> <img src="../images/noteq.gif"> <I>min</I>[<I>H</I>].<P>
<a name="0886_16d8">21-2 More Fibonacci-heap operations<a name="0886_16d8"><P>
<a name="0886_16d0"><a name="0886_16d1"><a name="0886_16d2"><a name="0886_16d3"><a name="0886_16d4"><a name="0886_16d5">We wish to augment a Fibonacci heap <I>H</I> to support two new operations without changing the amortized running time of any other Fibonacci-heap operations.<P>
<I><B>a.</I></B>     Give an efficient implementation of the operation <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>CHANGE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>(<I>H, x, k</I>), which changes the key of node <I>x</I> to the value <I>k</I>. Analyze the amortized running time of your implementation for the cases in which <I>k</I> is greater than, less than, or equal t