chap21.htm

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

<h2>Inserting a node</h2><P>
<a name="087b_16a0"><a name="087b_16a1">The following procedure inserts node <I>x</I> into Fibonacci heap <I>H</I>, assuming of course that the node has already been allocated and that <I>key</I>[<I>x</I>] has already been filled in.<P>
<pre><a name="087b_16a2">FIB-HEAP-INSERT(<I>H</I>, <I>x</I>)</sub></sup></pre><P>
<pre>1<I>  degree</I>[<I>x</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>2  <I>p</I>[<I>x</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>3  <I>child</I>[<I>x</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>4  <I>left</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>5  <I>right</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>6  <I>mark</I>[<I>x</I>] <img src="../images/arrlt12.gif"> FALSE</sub></sup></pre><P>
<pre>7  concatenate the root list containing <I>x</I> with root list <I>H</I> </sub></sup></pre><P>
<pre>8  <B>if</B> min[<I>H</I>] = NIL or <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>10  <I>n</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>n</I>[<I>H</I>] + 1</sub></sup></pre><P>
After lines 1-6 initialize the structural fields of node <I>x</I>, making it its own circular, doubly linked list , line 7 adds <I>x</I> to the root list of <I>H</I> in <I>O</I>(1) actual time. Thus, node <I>x</I> becomes a single-node heap-ordered tree, and thus an unordered binomial tree, in the Fibonacci heap. It has no children and is unmarked. Lines 8-9 then update the pointer to the minimum node of Fibonacci heap <I>H</I> if necessary. Finally, line 10 increments <I>n</I>[<I>H</I>] to reflect the addition of the new node. Figure 21.2 shows a node with key 21 inserted into the Fibonacci heap of Figure 21.1.<P>
Unlike the <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure, <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> makes no attempt to consolidate the trees within the Fibonacci heap. If <I>k</I> consecutive <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operations occur, then <I>k</I> single-node trees are added to the root list.<P>
<img src="425_a.gif"><P>
<h4><a name="087b_16a3">Figure 21.2 Inserting a node into a Fibonacci heap. (a) A Fibonacci heap H. (b) Fibonacci heap H after the node with key 21 has been inserted. The node becomes its own heap-ordered tree and is then added to the root list, becoming the left sibling of the root.<a name="087b_16a3"></sub></sup></h4><P>
To determine 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>INSERT</FONT>, let <I>H</I> be the input Fibonacci heap and <I>H'</I> be the resulting Fibonacci heap. Then, <I>t</I>(<I>H</I>') = <I>t</I>(<I>H</I>) + 1 and <I>m</I>(<I>H</I>') = <I>m</I>(<I>H</I>), and the increase in potential is<P>
<pre>((<I>t</I>(<I>H</I>) + 1) + 2<I>m</I>(<I>H</I>)) - (<I>t</I>(<I>H</I>) + 2<I>m</I>(<I>H</I>)) = 1 .</sub></sup></pre><P>
Since the actual cost is <I>O</I>(1), the amortized cost is <I>O</I>(1) + 1 = <I>O</I>(1).<P>
<P>







<h2>Finding the minimum node</h2><P>
<a name="087c_16a3"><a name="087c_16a4">The minimum node of a Fibonacci heap <I>H</I> is given by the pointer <I>min</I>[<I>H</I>], so we can find the minimum node in <I>O</I>(1) actual time. Because the potential of <I>H</I> does not change, the amortized cost of this operation is equal to its <I>O</I>(1) actual cost.<P>
<P>







<h2>Uniting two Fibonacci heaps</h2><P>
<a name="087d_16a5"><a name="087d_16a6">The following procedure unites Fibonacci heaps <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB>, destroying <I>H</I><SUB>1 </SUB>and <I>H</I><SUB>2</SUB> in the process.<P>
<pre><a name="087d_16a7">FIB-HEAP-UNION(<I>H</I><SUB>1,</SUB><I>H</I><SUB>2</SUB>)</sub></sup></pre><P>
<pre>1   <I>H</I> <img src="../images/arrlt12.gif"> MAKE-FIB-HEAP()</sub></sup></pre><P>
<pre>2   <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>min</I>[<I>H</I><SUB>1</SUB>]</sub></sup></pre><P>
<pre>3   concatenate the root list of <I>H</I><SUB>2</SUB> with the root list of <I>H</I></sub></sup></pre><P>
<pre>4   <B>if</B> (<I>min</I>[<I>H</I><SUB>1</SUB>] = NIL) or (<I>min</I>[<I>H</I><SUB>2</SUB>] <img src="../images/noteq.gif"> NIL and <I>min</I>[<I>H</I><SUB>2</SUB>] &lt; <I>min</I>[<I>H</I><SUB>1</SUB>])</sub></sup></pre><P>
<pre>5   <B>then</B> <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>min</I>[<I>H</I><SUB>2</SUB>]</sub></sup></pre><P>
<pre>6   <I>n</I>[<I>H</I>] <img src="../images/arrlt12.gif"> <I>n</I>[<I>H</I><SUB>1</SUB>] + <I>n</I>[<I>H</I><SUB>2</SUB>]</sub></sup></pre><P>
<pre>7   free the objects <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</sub></sup></pre><P>
<pre>8   <B>return</B> <I>H</I></sub></sup></pre><P>
Lines 1-3 concatenate the root lists of <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> into a new root list <I>H</I>. Lines 2, 4, and 5 set the minimum node of <I>H</I>, and line 6 sets <I>n</I>[<I>H</I>] to the total number of nodes. The Fibonacci heap objects <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> are freed in line 7, and line 8 returns the resulting Fibonacci heap <I>H</I>. As in the <FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure, no consolidation of trees occurs.<P>
The change in potential is<P>
<pre><img src="../images/phicap12.gif">(<I>H</I>) - (<img src="../images/phicap12.gif">(<I>H</I><SUB>1</SUB>) + <img src="../images/phicap12.gif">(<I>H</I><SUB>2</SUB>))</sub></sup></pre><P>
<pre>=  (<I>t</I>(<I>H</I>) + 2<I>m</I>(<I>H</I>)) - ((<I>t</I>(<I>H</I><SUB>1</SUB>) + 2 <I>m</I>(<I>H</I><SUB>1</SUB>)) + (<I>t</I>(<I>H</I><SUB>2</SUB>) + 2<I>m</I>(<I>H</I><SUB>2</SUB>)))</sub></sup></pre><P>
<pre>=  0,</sub></sup></pre><P>
because <I>t</I>(<I>H</I>) = <I>t</I>(<I>H</I><SUB>1</SUB>) + <I>t</I>(<I>H</I><SUB>2</SUB>) and <I>m</I>(<I>H</I>) = <I>m</I>(<I>H</I><SUB>1</SUB>) + <I>m</I>(<I>H</I><SUB>2</SUB>). 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>UNION</FONT> is therefore equal to its <I>O</I>(1) actual cost.<P>
<P>







<h2>Extracting the minimum node</h2><P>
<a name="087e_16a8"><a name="087e_16a9">The process of extracting the minimum node is the most complicated of the operations presented in this section. It is also where the delayed work of consolidating trees in the root list finally occurs. The following pseudocode extracts the minimum node. The code assumes for convenience that when a node is removed from a linked list, pointers remaining in the list are updated, but pointers in the extracted node are left unchanged. It also uses the auxiliary procedure <FONT FACE="Courier New" SIZE=2>CONSOLIDATE</FONT>, which will be presented shortly.<P>
<pre><a name="087e_16aa">FIB-HEAP-EXTRACT-MIN(<I>H</I>)</sub></sup></pre><P>
<pre>1  <I>z</I> <img src="../images/arrlt12.gif"> <I>min</I>[<I>H</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 for</B> each child <I>x</I> of <I>z</I></sub></sup></pre><P>
<pre>4               <B>do</B> add <I>x</I> to the root list of <I>H</I></sub></sup></pre><P>
<pre>5                  <I>p</I>[<I>x</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>6           remove <I>z</I> from the root list of <I>H</I></sub></sup></pre><P>
<pre>7           <B>if</B> <I>z</I> = <I>right</I>[<I>z</I>]</sub></sup></pre><P>
<pre>8              <B>then</B> <I>min</I>[<I>H</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>