chap20.htm

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

<h3>Representing binomial heaps</h3><P>
As shown in Figure 20.3(b), each binomial tree within a binomial heap is stored in the left-child, right-sibling representation of Section 11.4. Each node has a <I>key</I> field and any other satellite information required by the application. In addition, each node <I>x</I> contains pointers <I>p</I>[<I>x</I>] to its parent, <I>child</I> [<I>x</I>] to its leftmost child, and <I>sibling</I>[<I>x</I>] to the sibling of <I>x</I> immediately to its right. If node <I>x</I> is a root, then <I>p</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>. If node <I>x</I> has no children, then <I>child</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, and if<I> x</I> is the rightmost child of its parent, then <I>sibling</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Each node <I>x</I> also contains the field <I>degree</I>[<I>x</I>] , which is the number of children of <I>x</I>.<P>
<img src="405_a.gif"><P>
<h4><a name="0867_1665">Figure 20.4 The binomial tree B<SUB>4</SUB> with nodes labeled in binary by a postorder walk.<a name="0867_1665"></sub></sup></h4><P>
<a name="0867_1664">As Figure 20.3 also shows, the roots of the binomial trees within a binomial heap are organized in a linked list, which we refer to as the <I><B>root list</I></B>. The degrees of the roots strictly increase as we traverse the root list. By the second binomial-heap property, in an <I>n</I>-node binomial heap the degrees of the roots are a subset of {0, 1, . . . , <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>}. The <I>sibling</I> field has a different meaning for roots than for nonroots. If <I>x</I> is a root, then <I>sibling</I>[<I>x</I>] points to the next root in the root list. (As usual, <I>sibling</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT> if <I>x</I> is the last root in the root list.)<P>
A given binomial heap <I>H</I> is accessed by the field <I>head</I>[<I>H</I>], which is simply a pointer to the first root in the root list of <I>H</I>. If binomial heap <I>H</I> has no elements, then <I>head</I>[<I>H</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P>
<P>


<P>







<h2><a name="0868_0001">Exercises<a name="0868_0001"></h2><P>
<a name="0868_0002">20.1-1<a name="0868_0002"><P>
Suppose that <I>x</I> is a node in a binomial tree within a binomial heap, and assume that <I>sibling</I>[<I>x</I>] <img src="../images/noteq.gif"> <FONT FACE="Courier New" SIZE=2>NIL</FONT>. If <I>x</I> is not a root, how does <I>degree</I>[<I>sibling</I>[<I>x</I>]] compare to <I>degree</I>[<I>x</I>]? How about if <I>x</I> is a root?<P>
<a name="0868_0003">20.1-2<a name="0868_0003"><P>
If <I>x</I> is a nonroot node in a binomial tree within a binomial heap, how does <I>degree</I>[<I>p</I>[<I>x</I>]] compare to <I>degree</I>[<I>x</I>]?<P>
<a name="0868_0004">20.1-3<a name="0868_0004"><P>
Suppose we label the nodes of binomial tree <I>B<SUB>k</I></SUB> in binary by a postorder walk, as in Figure 20.4. Consider a node <I>x</I> labeled <I>l</I> at depth <I>i</I>, and let <I>j</I> = <I>k</I> - <I>i</I>. Show that <I>x</I> has <I>j</I> l's in its binary representation. How many binary <I>k</I>-strings are there that contain exactly <I>j</I> 1's? Show that the degree of <I>x</I> is equal to the number of 1's to the right of the rightmost 0 in the binary representation of <I>l</I>.<P>
<P>


<P>







<h1><a name="0869_0001">20.2 Operations on binomial heaps<a name="0869_0001"></h1><P>
In this section, we show how to perform operations on binomial heaps in the time bounds shown in Figure 20.1. We shall only show the upper bounds; the lower bounds are left as Exercise 20.2-10.<P>





<h2>Creating a new binomial heap</h2><P>
<a name="086a_1665"><a name="086a_1666">To make an empty binomial heap, the <FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> procedure simply allocates and returns an object <I>H</I>, where <I>head</I>[<I>H</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>. The running time is <img src="../images/bound.gif">(1).<P>
<P>







<h2>Finding the minimum key</h2><P>
<a name="086b_1667"><a name="086b_1668"><a name="086b_1669">The procedure <FONT FACE="Courier New" SIZE=2>BINOMIAL-</FONT><FONT FACE="Courier New" SIZE=2>HEAP-</FONT><FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> returns a pointer to the node with the minimum key in an <I>n</I>-node binomial heap <I>H</I>. This implementation assumes that there are no keys with value <img src="../images/infin.gif">. (See Exercise 20.2-5.)<P>
<pre>BINOMIAL-HEAP-MINIMUM(<I>H</I>)</sub></sup></pre><P>
<pre>1  <I>y</I> <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>2  <I>x</I> <img src="../images/arrlt12.gif"> <I>head</I>[<I>H</I>]</sub></sup></pre><P>
<pre>3  <I>min</I> <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>4  <B>while</B> <I>x</I> <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>5      <B>do if</B> <I>key</I>[<I>x</I>] &lt; <I>min</I></sub></sup></pre><P>
<pre>6            <B>then</B> <I>min</I> <img src="../images/arrlt12.gif"> <I>key</I>[<I>x</I>]</sub></sup></pre><P>
<pre>7                 <I>y</I> <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>8         <I>x</I> <img src="../images/arrlt12.gif"> <I>sibling</I>[<I>x</I>]</sub></sup></pre><P>
<pre>9  <B>return</B> <I>y</I></sub></sup></pre><P>
Since a binomial heap is heap-ordered, the minimum key must reside in a root node. The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> procedure checks all roots, which number 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> + 1, saving the current minimum in <I>min</I> and a pointer to the current minimum in <I>y</I>. When called on the binomial heap of Figure 20.3, <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> returns a pointer to the node with key 1.<P>
Because there are at most <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif">l</FONT>g <I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 1 roots to check, the running time of <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> is <I>O</I>(lg <I>n</I>).<P>
<P>







<h2>Uniting two binomial heaps </h2><P>
<a name="086c_166a"><a name="086c_166b">The operation of uniting two binomial heaps is used as a subroutine by most of the remaining operations. The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> procedure repeatedly links binomial trees whose roots have the same degree. The following procedure links the <I>B<SUB>k</I>-1 </SUB>tree rooted at node <I>y</I> to the <I>B<SUB>k</I>-1 </SUB>tree rooted at node <I>z</I>; that is, it makes <I>z</I> the parent of <I>y</I>. Node <I>z</I> thus becomes the root of a <I>B<SUB>k</I></SUB> tree.<P>
<pre><a name="086c_166c">BINOMIAL-LINK(<I>y,z</I>)</sub></sup></pre><P>
<pre>1  <I>p</I>[<I>y</I>] <img src="../images/arrlt12.gif"> <I>z</I></sub></sup></pre><P>
<pre>2  <I>sibling</I>[<I>y</I>] <img src="../images/arrlt12.gif"> <I>child</I>[<I>z</I>]</sub></sup></pre><P>
<pre>3  <I>child</I>[<I>z</I>] <img src="../images/arrlt12.gif"> <I>y</I></sub></sup></pre><P>
<pre>4  <I>degree</I>[<I>z</I>] <img src="../images/arrlt12.gif"> <I>degree</I>[<I>z</I>]+1</sub></sup></pre><P>
The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>LINK</FONT> procedure makes node <I>y</I> the new head of the linked list of node <I>z</I>'s children in <I>O</I>(1) time. It works because the left-child, right-sibling representation of each binomial tree matches the ordering property of the tree: in a <I>B<SUB>k</I> </SUB>tree, the leftmost child of the root is the root of a <I>B<SUB>k</I>-1<I> </I></SUB>tree.<P>
The following procedure unites binomial heaps <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB>, returning the resulting heap. It destroys the representations of <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2 </SUB>in the process. Besides <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>LINK</FONT>, the procedure uses an auxiliary procedure <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT> that merges the root lists of <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> into a single linked list that is sorted by degree into monotonically increasing order. The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT> procedure, whose pseudocode we leave as Exercise 20.2-2, is similar to the <FONT FACE="Courier New" SIZE=2>MERGE</FONT> procedure in Section 1.3.1.<P>
<img src="408_a.gif"><P>
<a name="086c_166d">Figure 20.5 shows an example of <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> in which all four cases given in the pseudocode occur.<P>
<a name="086c_166e">The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> procedure has two phases. The first phase, performed by the call of <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT>, merges the root lists of binomial heaps <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> into a single linked list <I>H</I> that is sorted by degree into monotonically increasing order. There might be as many as two roots (but no more) of each degree, however, so the second phase links roots of equal degree until at most one root remains of each degree. Because the linked list <I>H</I> is sorted by degree, we can perform all the link operations quickly.<P>
In detail, the procedure works as follows. Lines 1-3 start by merging the root lists of binomial heaps <I>H</I><SUB>1 </SUB>and <I>H</I><SUB>2 </SUB>into a single root list <I>H</I>. The root lists of <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> are sorted by strictly increasing degree, and <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT> returns a root list <I>H</I> that is sorted by monotonically increasing degree. If the root lists of <I>H</I><SUB>1 </SUB>and <I>H</I><SUB>2 </SUB>have <I>m</I> roots altogether, <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT> runs in <I>O</I>(<I>m</I>) time by repeatedly examining the roots at the heads of the two root lists and appending the root with the lower degree to the output root list, removing it from its input root list in the process.<P>
The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> procedure next initializes some pointers into the root list of <I>H</I>. First, it simply returns in lines 4-5 if it happens to be uniting two empty binomial heaps. From line 6 on, therefore, we know that <I>H</I> has at least one root. Throughout the procedure, we maintain three pointers into the root list:<P>
<img src="../images/dot12.gif">     <I>x</I> points to the root currently being examined,<P>
<img src="../images/dot12.gif">     <I>prev-x</I> points to the root preceding <I>x</I> on the root list: <I>sibling</I>[<I>prev-x</I>] = <I>x</I>, and<P>
<img src="../images/dot12.gif">     <I>next-x</I> points to the root following <I>x</I> on the root list: <I>sibling</I>[<I>x</I>] = <I>next-x</I>.<P>