chap20.htm

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

<img src="416_a.gif"><P>
<h4><a name="0870_167b">Figure 20.8 The action 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>DECREASE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>KEY</FONT></FONT></FONT></FONT></FONT></FONT></FONT>. (a) The situation just before line 5 of the first iteration of the while loop. Node y has had its key decreased to 7, which is less than the key of y's parent z. (b) The keys of the two nodes are exchanged, and the situation just before line 5 of the second iteration is shown. Pointers y and z have moved up one level in the tree, but heap order is still violated. (c) After another exchange and moving pointers y and z up one more level, we finally find that heap order is satisfied, so the while loop terminates.<a name="0870_167b"></sub></sup></h4><P>
<pre><a name="0870_167a">BINOMIAL-HEAP-DELETE(<I>H,x</I>)</sub></sup></pre><P>
<pre>1 BINOMIAL-HEAP-DECREASE-KEY(<I>H,x,</I>-<img src="../images/infin.gif">)</sub></sup></pre><P>
<pre>2 BINOMIAL-HEAP-EXTRACT-MIN(<I>H</I>)</sub></sup></pre><P>
The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> procedure makes node <I>x</I> have the unique minimum key in the entire binomial heap by giving it a key of -<img src="../images/infin.gif">. (Exercise 20.2-6 deals with the situation in which -<img src="../images/infin.gif"><I><FONT FACE="Times New Roman" SIZE=4> </I></FONT>cannot appear as a key, even temporarily.) It then bubbles this key and the associated satellite information up to a root by calling <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>. This root is then removed from <I>H</I> by a call of <FONT FACE="Courier New" SIZE=2>BINOMIAL</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>
The <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP-</FONT><FONT FACE="Courier New" SIZE=2>DELETE</FONT> procedure takes <I>O</I>(lg <I>n</I>) time.<P>
<P>







<h2><a name="0871_1681">Exercises<a name="0871_1681"></h2><P>
<a name="0871_1682">20.2-1<a name="0871_1682"><P>
Give an example of two b<I>inary</I> heaps with <I>n</I> elements each such that <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> takes <img src="../images/bound.gif">(<I>n</I>) time on the concatenation of their arrays.<P>
<a name="0871_1683">20.2-2<a name="0871_1683"><P>
<a name="0871_167b">Write pseudocode for <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MERGE</FONT>.<P>
<a name="0871_1684">20.2-3<a name="0871_1684"><P>
Show the binomial heap that results when a node with key 24 is inserted into the binomial heap shown in Figure 20.7(d).<P>
<a name="0871_1685">20.2-4<a name="0871_1685"><P>
Show the binomial heap that results when the node with key 28 is deleted from the binomial heap shown in Figure 20.8(c).<P>
<a name="0871_1686">20.2-5<a name="0871_1686"><P>
<a name="0871_167c">Explain why 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 might not work correctly if keys can have the value <I><FONT FACE="Times New Roman" SIZE=4></I><img src="../images/infin.gif"></FONT><I></I>. Rewrite the pseudocode to make it work correctly in such cases.<P>
<a name="0871_1687">20.2-6<a name="0871_1687"><P>
<a name="0871_167d">Suppose there is no way to represent the key - <img src="../images/infin.gif">. Rewrite the <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> procedure to work correctly in this situation. It should still take <I>O</I>(lg <I>n</I>) time.<P>
<a name="0871_1688">20.2-7<a name="0871_1688"><P>
<a name="0871_167e"><a name="0871_167f">Discuss the relationship between inserting into a binomial heap and incrementing a binary number and the relationship between uniting two binomial heaps and adding two binary numbers.<P>
<a name="0871_1689">20.2-8<a name="0871_1689"><P>
<a name="0871_1680">In light of Exercise 20.2-7, rewrite <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> to insert a node directly into a binomial heap without calling <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT>.<P>
<a name="0871_168a">20.2-9<a name="0871_168a"><P>
Show that if root lists are kept in strictly decreasing order by degree (instead of strictly increasing order), each of the binomial heap operations can be implemented without changing its asymptotic running time.<P>
<a name="0871_168b">20.2-10<a name="0871_168b"><P>
Find inputs that cause <FONT FACE="Courier New" SIZE=2>BINOMIAL</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>, <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>, and <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> to run in <img src="../images/omega12.gif">(lg <I>n</I>) time. Explain why the worst-case running times of <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, and <FONT FACE="Courier New" SIZE=2>BINOMIAL</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>UNION</FONT> are <img src="417_a.gif"> (lg <I>n</I>)<I> </I>but not <img src="../images/omega12.gif">(lg <I>n</I>). (See Problem 2-5.)<P>
<P>


<P>







<h1><a name="0872_168f">Problems<a name="0872_168f"></h1><P>
<a name="0872_1690">20-1     2-3-4 heaps<a name="0872_1690"><P>
<a name="0872_1681"><a name="0872_1682"><a name="0872_1683"><a name="0872_1684"><a name="0872_1685">Chapter 19 introduced the 2-3-4 tree, in which every internal node (other than possibly the root) has two, three, or four children and all leaves have the same depth. In this problem, we shall implement <I><B>2-3-4 heaps</I></B><I>,</I> which support the mergeable-heap operations.<P>
The 2-3-4 heaps differ from 2-3-4 trees in the following ways. In 2-3-4 heaps, only leaves store keys, and each leaf <I>x</I> stores exactly one key in the field <I>key</I>[<I>x</I>]. There is no particular ordering of the keys in the leaves; that is, from left to right, the keys may be in any order. Each internal node <I>x </I>contains a value <I>small</I>[<I>x</I>] that is equal to the smallest key stored in any leaf in the subtree rooted at <I>x</I>. The root <I>r </I>contains a field <I>height </I>[<I>r</I>]<I> </I>that is the height of the tree. Finally, 2-3-4 heaps are intended to be kept in main memory, so that disk reads and writes are not needed.<P>
Implement the following 2-3-4 heap operations. Each of the operations in parts (a)-(e) should run in <I>O</I>(lg <I>n</I>) time on a 2-3-4 heap with <I>n</I> elements. The <FONT FACE="Courier New" SIZE=2>UNION</FONT> operation in part (f) should run in <I>O</I>(lg <I>n</I>) time, where <I>n</I> is the number of elements in the two input heaps.<P>
<a name="0872_1686"><I><B>a</I>.</B>     <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, which returns a pointer to the leaf with the smallest key.<P>
<a name="0872_1687"><I><B>b</I>.</B>     <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>, which decreases the key of a given leaf <I>x</I> to a given value <I>k</I> <img src="../images/lteq12.gif"> <I>key</I>[<I>x</I>].<P>
<a name="0872_1688"><B>c.</B>     <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, which inserts leaf <I>x</I> with key <I>k</I>.<P>
<a name="0872_1689"><I><B>d</I>.</B>     <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, which deletes a given leaf <I>x</I>.<P>
<a name="0872_168a"><I><B>e</I>.</B>     <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT>, which extracts the leaf with the smallest key.<P>
<a name="0872_168b"><I><B>f.</I></B>     <FONT FACE="Courier New" SIZE=2>UNION</FONT>, which unites two 2-3-4 heaps, returning a single 2-3-4 heap and destroying the input heaps.<P>
<a name="0872_1691">20-2     Minimum-spanning-tree algorithm using mergeable heaps<a name="0872_1691"><P>
<a name="0872_168c"><a name="0872_168d">Chapter 24 presents two algorithms to solve the problem of finding a minimum spanning tree of an undirected graph. Here, we shall see how mergeable heaps can be used to devise a different minimum-spanning-tree algorithm.<P>
We are given a connected, undirected graph <I>G </I>=<I> </I>(<I>V, E</I>) with a weight function <I>w: E </I><img src="../images/arrow12.gif"><I> </I><B>R</B><I>. </I>We call<I> w</I>(<I>u,v</I>) the weight of edge (<I>u, v</I>). We wish to find a minimum spanning tree for <I>G</I>: an acyclic subset <I>T</I> <img src="../images/rgtubar.gif"> <I>E</I> that connects all the vertices in <I>V</I> and whose total weight<P>
<img src="418_a.gif"><P>
is minimized.<P>
The following pseudocode, which can be proven correct using techniques from Section 24.1, constructs a minimum spanning tree <I>T</I>. It maintains a partition {<I>V<SUB>i</I></SUB>} of the vertices of<I> V</I> and, with each set <I>V<SUB>i</I></SUB>, a set<P>
<pre><I>E<SUB>i</I></SUB> <img src="../images/rgtubar.gif"> {(<I>u,v</I>): <I>u</I> <img src="../images/memof12.gif"> <I>V<SUB>i</I></SUB> or <I>v </I><img src="../images/memof12.gif"><I>V<SUB>i</I></SUB>}</sub></sup></pre><P>
of edges incident on vertices in <I>V<SUB>i</I></SUB>.<P>
<img src="419_a.gif"><P>
<a name="0872_168e">Describe how to implement this algorithm using the mergeable-heap operations given in Figure 20.1. Give the running time of your implementation, assuming that the mergeable heaps are implemented by binomial heaps.<P>
<P>







<h1>Chapter notes</h1><P>
Binomial heaps were introduced in 1978 by Vuillemin [196]. Brown[36, 37] studied their properties in detail.<P>
<P>


<P>
<P>
<center>Go to <a href="chap21.htm">Chapter 21</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>