chap20.htm

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

Initially, there are at most two roots on the root list <I>H</I> of a given degree: because <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> were binomial heaps, they each had only one root of a given degree. Moreover, B<FONT FACE="Courier New" SIZE=2>INOMIAL-</FONT>H<FONT FACE="Courier New" SIZE=2>EAP-</FONT><FONT FACE="Courier New" SIZE=2>MERGE</FONT> guarantees us that if two roots in <I>H</I> have the same degree, they are adjacent in the root list.<P>
In fact, during the execution of B<FONT FACE="Courier New" SIZE=2>INOMlAL-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT>, there may be three roots of a given degree appearing on the root list <I>H</I> at some time. We shall see in a moment how this situation could occur. At each iteration of the <B>while</B> loop of lines 9-21, therefore, we decide whether to link <I>x</I> and <I>next-x</I> based on their degrees and possibly the degree of <I>sibling</I>[<I>next-x</I>]. An invariant of the loop is that each time we start the body of the loop, both <I>x</I> and <I>next-x</I> are non-<FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P>
Case 1, shown in Figure 20.6(a), occurs when <I>degree</I>[<I>x</I>] <img src="../images/noteq.gif"> <I>degree</I>[<I>next-x</I>], that is, when <I>x</I> is the root of a <I>B<SUB>k</I></SUB>-tree and <I>next-x</I> is the root of a <I>B<SUB>l</I></SUB>-tree for some <I>l</I> &gt; <I>k.</I> Lines 11-12 handle this case. We don't link <I>x</I> and <I>next-x,</I> so we simply march the pointers one position further down the list. Updating <I>next-x</I> to point to the node following the new node <I>x</I> is handled in line 21, which is common to every case.<P>
Case 2, shown in Figure 20.6(b), occurs when <I>x</I> is the first of three roots of equal degree, that is, when<P>
<pre><I>degree</I>[<I>x</I>] = <I>degree</I>[<I>next</I>-<I>x</I>]<I> </I>=<I> degree</I>[<I>sibling</I>[<I>next</I>-<I>x</I>]]<I>.</I></sub></sup></pre><P>
We handle this case in the same manner as case 1: we just march the pointers one position further down the list. Line 10 tests for both cases 1 and 2, and lines 11-12 handle both cases.<P>
Cases 3 and 4 occur when <I>x</I> is the first of two roots of equal degree, that is, when<P>
<pre><I>degree</I>[<I>x</I>] = <I>degree</I>[<I>next</I>-<I>x</I>] <img src="../images/noteq.gif"> <I>degree</I>[<I>sibling</I>[<I>next</I>-<I>x</I>]].</sub></sup></pre><P>
These cases may occur on the next iteration after any case, but one of them always occurs immediately following case 2. In cases 3 and 4, we link <I>x</I> and <I>next-x.</I> The two cases are distinguished by whether <I>x</I> or <I>next-x</I> has the smaller key, which determines the node that will be the root after the two are linked.<P>
In case 3, shown in Figure 20.6(c), <I>key</I>[<I>x</I>] <img src="../images/lteq12.gif"> <I>key</I>[<I>next-x</I>], so <I>next-x</I> is linked to <I>x.</I> Line 14 removes <I>next-x</I> from the root list, and line 15 makes <I>next-x</I> the leftmost child of <I>x.</I><P>
<img src="410_a.gif"><P>
<h4><a name="086c_166f">Figure 20.5 The execution of <FONT FACE="Courier New" SIZE=2>BINOMIAL-<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>UNION.</FONT></FONT></FONT></FONT></FONT>(a) Binomial heaps H<SUB>1 </SUB>and H<SUB>2.</SUB> (b) Binomial heap H is the output of <FONT FACE="Courier New" SIZE=2>BINOMIAL-<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>MERGE(H<SUB>1</SUB>,H<SUB>2</SUB>)</FONT></FONT></FONT></FONT></FONT>. Initially, x is the first root on the root list of H. Because both x and next-x have degree 0 and key[x] &lt; key[next-x], case 3 applies. (c) After the link occurs, x is the first of three roots with the same degree, so case 2 applies. (d) After all the pointers move down one position in the root list, case 4 applies, since x is the first of two roots of equal degree. (e) After the link occurs, case 3 applies. (f) After another link, case 1 applies, because x has degree 3 and next-x has degree 4. This iteration of the while loop is the last, because after the pointers move down one position in the root list, next-x = <FONT FACE="Courier New" SIZE=2>NIL<FONT FACE="Times New Roman" SIZE=2>.<a name="086c_166f"></FONT></FONT></sub></sup></h4><P>
<img src="411_a.gif"><P>
In case 4, shown in Figure 20.6(d), <I>next-x</I> has the smaller key, so <I>x</I> is linked to <I>next-x.</I> Lines 16-18 remove <I>x</I> from the root list, which has two cases depending on whether <I>x</I> is the first root on the list (line 17) or is not (line 18). Line 19 then makes <I>x</I> the leftmost child of <I>next-x</I>, and line 20 updates <I>x</I> for the next iteration.<P>
Following either case 3 or case 4, the setup for the next iteration of the <B>while</B> loop is the same. We have just linked two <I>B<SUB>k</I></SUB>-trees to form a <I>B<SUB>k</I>+l</SUB>-tree, which <I>x</I> now points to. There were already zero, one, or two other <I>B<SUB>k</I>+1-</SUB>trees on the root list from the output of B<FONT FACE="Courier New" SIZE=2>INOMIAL-</FONT>H<FONT FACE="Courier New" SIZE=2>EAP-</FONT><FONT FACE="Courier New" SIZE=2>MERGE</FONT>, so <I>x</I> is now the first of either one, two, or three <I>B<SUB>k</I>+l</SUB>-trees on the root list. If <I>x</I> is the only one, then we enter case 1 in the next iteration: <I>degree</I> [<I>x</I>] <img src="../images/noteq.gif"> <I>degree</I>[<I>next-x</I>]. If <I>x</I> is the first of two, then we enter either case 3 or case 4 in the next iteration. It is when <I>x</I> is the first of three that we enter case 2 in the next iteration.<P>
The running time of B<FONT FACE="Courier New" SIZE=2>INOMIAL-</FONT>H<FONT FACE="Courier New" SIZE=2>EAP-</FONT><FONT FACE="Courier New" SIZE=2>UNION</FONT> is <I>O</I>(1g <I>n</I>), where <I>n</I> is the total number of nodes in binomial heaps <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB>. We can see this as follows. Let <I>H</I><SUB>1</SUB> contain <I>n</I><SUB>1</SUB> nodes and <I>H</I><SUB>2</SUB> contain <I>n</I><SUB>2</SUB> nodes, so that <I>n</I> = <I>n</I><SUB>1</SUB> + <I>n</I><SUB>2</SUB>. Then, <I>H</I><SUB>1</SUB> contains at most <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><SUB>1</SUB><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 1 roots and <I>H</I><SUB>2</SUB> contains at most <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 1 roots, so <I>H</I> contains at most <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><SUB>1</SUB><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 2 <img src="../images/lteq12.gif"> 2 <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 2 = <I>O</I>(1g <I>n</I>) roots immediately after the call of B<FONT FACE="Courier New" SIZE=2>INOMIAL-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT>. The time to perform <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT> is thus <I>O</I>(lg <I>n</I>). Each iteration of the <B>while</B> loop takes <I>O</I>(1) time, and there are at most <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><SUB>1</SUB><img src="../images/hfbrdr12.gif"> + <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><SUB>2</SUB><img src="../images/hfbrdr12.gif"> + 2 iterations because each iteration either advances the pointers one position down the root list of <I>H</I> or removes a root from the root list. The total time is thus <I>O</I>(lg <I>n</I>).<P>
<img src="412_a.gif"><P>
<h4><a name="086c_1670">Figure 20.6 The four cases that occur in <FONT FACE="Courier New" SIZE=2>BINOMIAL-<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>UNION.</FONT></FONT></FONT></FONT></FONT> Labels a, b, c, and d serve only to identify the roots involved; they do not indicate the degrees or keys of these roots. In each case, x is the root of a B<SUB>k</SUB>-tree and l &gt; k. (a) Case 1: degree[x] <img src="../images/noteq.gif"> degree[next-x]. The pointers move one position further down the root list. (b) Case 2: degree[x] = degree[next-x]<SUB> = </SUB>degree[sibling[next-x]]. Again, the pointers move one position further down the list, and the next iteration executes either case 3 or case 4. (c) Case 3: degree[x] = degree[next-x] <img src="../images/noteq.gif"> degree[sibling[next-x] and key[x] <img src="../images/lteq12.gif"> key[next-x]. We remove next-x from the root list and link it to x, creating a<SUB> </SUB>B<SUB>k+1</SUB>-tree. (d) Case 4: degree[x] = degree[next-x] <img src="../images/noteq.gif"> degree[sibling[next-x]] and key[next-x] <img src="../images/lteq12.gif"> key[x]. We remove x from the root list and link it to next-x, again creating a B <SUB>k+1</SUB>-tree.<a name="086c_1670"></sub></sup></h4><P>
<P>







<h2>Inserting a node</h2><P>
<a name="086d_166f"><a name="086d_1670">The following procedure inserts node <I>x</I> into binomial heap <I>H,</I> assuming of course that node <I>x</I> has already been allocated and <I>key</I>[<I>x</I>] has already been filled in.<P>
<pre><a name="086d_1671">BINOMIAL-HEAP-INSERT(<I>H</I>,<I>x</I>)</sub></sup></pre><P>
<pre>1  <I>H</I>'<I> </I><img src="../images/arrlt12.gif"><I> </I>MAKE-BINOMIAL-HEAP()</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>sibling</I>[<I>x</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>5  <I>degree</I>[<I>x</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>6  <I>head</I>[<I>H</I>'] <img src="../images/arrlt12.gif"> x</sub></sup></pre><P>
<pre>7  <I>H </I><img src="../images/arrlt12.gif"> BINOMIAL-HEAP-UNION(<I>H,H</I>')</sub></sup></pre><P>
The procedure simply makes a one-node binomial heap <I>H</I>' in <I>O</I>(1) time and unites it with the <I>n</I>-node binomial heap <I>H</I> in <I>O</I>(1g <I>n</I>) time. The call to <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> takes care of freeing the temporary binomial heap <I>H</I>'. (A direct implementation that does not call <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> is given as Exercise 20.2-8.)<P>
<P>







<h2>Extracting the node with minimum key</h2><P>
<a name="086e_1672"><a name="086e_1673">The following procedure extracts the node with the minimum key from binomial heap <I>H</I> and returns a pointer to the extracted node.<P>
<pre><a name="086e_1674">BINOMIAL-HEAP-EXTRACT-MIN(<I>H</I>)</sub></sup></pre><P>
<pre>1  find the root <I>x</I> with the minimum key in the root list of <I>H,</I></sub></sup></pre><P>
<pre>and remove <I>x</I> from the root list of <I>H</I></sub></sup></pre><P>
<pre>2  <I>H</I>' <img src="../images/arrlt12.gif"> MAKE-BINOMIAL-HEAP()</sub></sup></pre><P>
<pre>3  reverse the order of the linked list of <I>x</I>'s children,</sub></sup></pre><P>
<pre>and set <I>head</I>[<I>H</I>'] to point to the head of the resulting list</sub></sup></pre><P>
<pre>4  <I>H</I> <SUB><img src="../images/arrlt12.gif"> BINOMIAL-HEAP-UNION(<I>H</I>,<I>H</I></SUB>'<I>)</I></sub></sup></pre><P>
<pre>5  <B>return</B> <I>x</I></sub></sup></pre><P>
This procedure works as shown in Figure 20.7. The input binomial heap <I>H </I>is shown in Figure 20.7(a). Figure 20.7(b) shows the situation after line 1: the root <I>x</I> with the minimum key has been removed from the root list of <I>H</I>. If <I>x</I> is the root of a <I>B<SUB>k</SUB>-</I>tree, then by property 4 of Lemma 20.1, <I>x</I>'s children, from left to right, are roots of <I>B<SUB>k</I></SUB>-<SUB>1</SUB>-, <I>B<SUB>k</I></SUB>-<SUB>2</SUB>-, . . . , <I>B</I><SUB>0</SUB>-trees. Figure 20.7(c) shows that by reversing the list of <I>x</I>'s children in line 3, we have a binomial heap <I>H</I>' that contains every node in <I>x</I>'s tree except for <I>x</I> itself. Because <I>x</I>'s tree is removed from <I>H</I> in line 1, the binomial heap that results from uniting <I>H</I> and <I>H</I>' in line 4, shown in Figure 20.7(d), contains all the nodes originally in <I>H</I> except for <I>x</I>. Finally, line 5 returns <I>x</I>.<P>
<img src="414_a.gif"><P>
<h4><a name="086e_1675">Figure 20.7 The action of B<FONT FACE="Courier New" SIZE=2>INOMIAL-<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 FACE="Times New Roman" SIZE=2>. (a) A binomial heap H. (b) The root x with minimum key is removed from the root list of H. (c) The linked list of x's children is reversed, giving another binomial heap H'. (d) The result of uniting H and H'.<a name="086e_1675"></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></sub></sup></h4><P>
Since each of lines 1-4 takes <I>O</I>(lg <I>n</I>) time if <I>H</I> has <I>n</I> nodes, B<FONT FACE="Courier New" SIZE=2>INOMIAL-</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> runs in <I>O</I>(lg <I>n</I>) time.<P>
<P>







<h2>Decreasing a key</h2><P>
<a name="086f_1675"><a name="086f_1676">The following procedure decreases the key of a node <I>x</I> in a binomial heap <I>H</I> to a new value <I>k</I>. It signals an error if <I>k</I> is greater than <I>x</I>'s current key.<P>
<pre><a name="086f_1677">BINOMIAL-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>x</I></sub></sup></pre><P>
<pre>5  <I>z</I> <img src="../images/arrlt12.gif"> <I>p</I>[<I>y</I>]</sub></sup></pre><P>
<pre>6  <B>while</B><I> z</I> <img src="../images/noteq.gif"> NIL and <I>key</I>[<I>y</I>] &lt; <I>key</I>[<I>z</I>]</sub></sup></pre><P>
<pre>7      <B>do</B> exchange <I>key</I>[<I>y</I>] <img src="../images/dblarr12.gif"> <I>key</I>[<I>z</I>]</sub></sup></pre><P>
<pre>8         <img src="415_a.gif"> If <I>y</I> and <I>z</I> have satellite fields, exchange them, too.</sub></sup></pre><P>
<pre>9         <I>y</I> <img src="../images/arrlt12.gif"> <I>z</I></sub></sup></pre><P>
<pre>10        <I>z</I> <img src="../images/arrlt12.gif"> <I>p</I>[<I>y</I>]</sub></sup></pre><P>
As shown in Figure 20.8, this procedure decreases a key in the same manner as in a binary heap: by &quot;bubbling up&quot; the key in the heap. After ensuring that the new key is in fact no greater than the current key and then assigning the new key to <I>x</I>, the procedure goes up the tree, with <I>y </I>initially pointing to node <I>x</I>. In each iteration of the <B>while</B> loop of lines 6-10, <I>key</I>[<I>y</I>] is checked against the key of <I>y'</I>s parent <I>z</I>. If<I> y</I> is the root or <I>key</I>[<I>y</I>] <img src="../images/gteq.gif"> <I>key</I>[<I>z</I>], the binomial tree is now heap-ordered. Otherwise, node <I>y </I>violates heap ordering, so its key is exchanged with the key of its parent <I>z</I>, along with any other satellite information. The procedure then sets <I>y</I> to <I>z</I>, going up one level in the tree, and continues with the next iteration.<P>
The <FONT FACE="Courier New" SIZE=2>BINOMIAL-</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>(lg <I>n</I>) time. By property 2 of Lemma 20.1, the maximum depth of <I>x</I> is <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg<I> n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>, so the <B>while</B> loop of lines 6-10 iterates at most <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg<I> n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> times.<P>
<P>







<h2>Deleting a key</h2><P>
<a name="0870_1678"><a name="0870_1679">It is easy to delete a node <I>x'</I>s key and satellite information from binomial heap <I>H</I> in <I>O</I>(lg<I> n</I>) time. The following implementation assumes that no node currently in the binomial heap has a key of - <img src="../images/infin.gif"><FONT FACE="Times New Roman" SIZE=4>.</FONT><P>