chap07.htm

介绍算法的书籍

What is the effect of calling <FONT FACE="Courier New" SIZE=2>HEAPIFY </FONT>(<I>A</I>, <I>i</I>) for <I>i</I> &gt; <I>heap-size </I>[<I>A</I>]/2?<P>
<a name="0769_1320">7.2-4<a name="0769_1320"><P>
The code for <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> that uses an iterative control construct (a loop) instead of recursion.<P>
<a name="0769_1321">7.2-5<a name="0769_1321"><P>
Show that the worst-case running time of <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> on a heap of size <I>n </I>is <img src="../images/omega12.gif">(lg <I>n</I>). (<I>Hint</I>: For a heap with <I>n</I> nodes, give node values that cause <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> to be called recursively at every node on a path from the root down to a leaf.)<P>
<P>


<P>







<h1><a name="076a_131e">7.3 Building a heap<a name="076a_131e"></h1><P>
<a name="076a_131c">We can use the procedure <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> in a bottom-up manner to convert an array <I>A</I>[1 . . <I>n</I>], where <I>n</I> = <I>length</I>[<I>A</I>], into a heap. Since the elements in the subarray <I>A</I>[(<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + l) . . <I>n</I>] are all leaves of the tree, each is a 1-element heap to begin with. The procedure <FONT FACE="Courier New" SIZE=2>BUILD-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT> goes through the remaining nodes of the tree and runs <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> on each one. The order in which the nodes are processed guarantees that the subtrees rooted at children of a node <I>i</I> are heaps before <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> is run at that node.<P>
<pre>BUILD-HEAP(<I>A</I>)</sub></sup></pre><P>
<pre>1  <I>heap-size</I>[<I>A</I>] <img src="../images/arrlt12.gif"><I> length</I>[<I>A</I>]</sub></sup></pre><P>
<pre>2  <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> <img src="../images/hfbrdl12.gif"><I>length</I>[<I>A</I>]/2<img src="../images/hfbrdr12.gif"><B>downto</B> 1</sub></sup></pre><P>
<pre>3        <B>do</B> HEAPIFY(<I>A, i</I>)</sub></sup></pre><P>
<a name="076a_131d">Figure 7.3 shows an example of the action of <FONT FACE="Courier New" SIZE=2>BUILD-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT>.<P>
We can compute a simple upper bound on the running time of <FONT FACE="Courier New" SIZE=2>BUILD-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT> as follows. Each call to <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> costs <I>O</I>(lg <I>n</I>) time, and there are <I>O</I>(<I>n</I>) such calls. Thus, the running time is at most <I>O(n</I> lg <I>n</I>). This upper bound, though correct, is not asymptotically tight.<P>
We can derive a tighter bound by observing that the time for <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. Our tighter analysis relies on the property that in an <I>n</I>-element heap there are at most <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<I><SUP>h</I>+1</SUP><img src="../images/hfbrur14.gif"> nodes of height <I>h </I>(see Exercise 7.3-3).<P>
The time required by <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> when called on a node of height <I>h</I> is <I>O(h</I>), so we can express the total cost of <FONT FACE="Courier New" SIZE=2>BUILD-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT> as<P>
<img src="145_a.gif"><P>
<h4><a name="076a_131f">(7.2)<a name="076a_131f"></sub></sup></h4><P>
The last summation can be evaluated by substituting <I>x</I> = 1/2 in the formula (3.6), which yields<P>
<img src="145_b.gif"><P>
Thus, the running time of <FONT FACE="Courier New" SIZE=2>BUILD-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT> can be bounded as<P>
<img src="145_c.gif"><P>
Hence, we can build a heap from an unordered array in linear time.<P>
<img src="146_a.gif"><P>
<h4><a name="076a_1320">Figure 7.3 The operation of <FONT FACE="Courier New" SIZE=2>BUILD<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT></FONT></FONT>, showing the data structure before the call to <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> in line 3 of <FONT FACE="Courier New" SIZE=2>BUILD<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT></FONT></FONT>. (a) A 10-element input array A and the binary tree it represents. The figure shows that the loop index i points to node 5 before the call <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT>(A, i). (b) The data structure that results. The loop index i for the next iteration points to node 4. (c)-(e) Subsequent iterations of the for loop in <FONT FACE="Courier New" SIZE=2>BUILD<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT></FONT></FONT>. Observe that whenever <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> is called on a node, the two subtrees of that node are both heaps. (f) The heap after <FONT FACE="Courier New" SIZE=2>BUILD<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT></FONT></FONT> finishes.<a name="076a_1320"></sub></sup></h4><P>





<h2><a name="076b_131f">Exercises<a name="076b_131f"></h2><P>
<a name="076b_1320">7.3-1<a name="076b_1320"><P>
Using Figure 7.3 as a model, illustrate the operation of <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> on the array <I>A</I> = <img src="../images/lftwdchv.gif">5, 3, 17, 10, 84, 19, 6, 22, 9<img src="../images/wdrtchv.gif">.<P>
<a name="076b_1321">7.3-2<a name="076b_1321"><P>
Why do we want the loop index<I> i</I> in line 2 of <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> to decrease from <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>length</I></FONT>[<I>A</I>]/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"><FONT FACE="Courier New" SIZE=2> </FONT></FONT>to<FONT FACE="Courier New" SIZE=2> </FONT>1 rather than increase from 1 to <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>length</I></FONT>[<I>A</I>]/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif">?</FONT><P>
<a name="076b_1322">7.3-3<a name="076b_1322"><P>
<a name="076b_131e">Show that there are at most <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<I><SUP>h</I>+1</SUP><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> nodes of height <I>h</I> in any <I>n</I>-element heap.<P>
<P>


<P>







<h1><a name="076c_1320">7.4 The heapsort algorithm<a name="076c_1320"></h1><P>
<a name="076c_131f">The heapsort algorithm starts by using <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> to build a heap on the input array <I>A</I>[1 . . <I>n</I>], where <I>n</I> = <I>length</I>[<I>A</I>]. Since the maximum element of the array is stored at the root <I>A</I>[1], it can be put into its correct final position by exchanging it with <I>A</I>[<I>n</I>]. If we now "discard" node <I>n</I> from the heap (by decrementing <I>heap-size</I>[<I>A</I>]), we observe that <I>A</I>[1 <I>. . </I>(<I>n - </I>1)]<I> </I>can easily be made into a heap. The children of the root remain heaps, but the new root element may violate the heap property (7.1). All that is needed to restore the heap property, however, is one call to <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT>(<I>A</I>, 1), which leaves a heap in <I>A</I>[1 <I>. . </I>(<I>n -</I> 1)]. The heapsort algorithm then repeats this process for the heap of size <I>n</I> - 1 down to a heap of size 2.<P>
<pre>HEAPSORT(<I>A</I>)</sub></sup></pre><P>
<pre>1  BUILD-HEAP(<I>A</I>)</sub></sup></pre><P>
<pre>2  <B>for </B><I>i </I><img src="../images/arrlt12.gif"><I> length</I>[<I>A</I>] <B>downto</B> 2</sub></sup></pre><P>
<pre>3        <B>do</B> exchange <I>A</I>[1] <img src="../images/dblarr12.gif"> <I>A</I>[i]</sub></sup></pre><P>
<pre>4           <I>heap-size</I>[<I>A</I>] <img src="../images/arrlt12.gif"> <I>heap-size</I>[<I>A</I>] -1</sub></sup></pre><P>
<pre>5           HEAPIFY(<I>A</I>, 1)</sub></sup></pre><P>
Figure 7.4 shows an example of the operation of heapsort after the heap is initially built. Each heap is shown at the beginning of an iteration of the <B>for</B> loop in line 2.<P>
The <FONT FACE="Courier New" SIZE=2>HEAPSORT</FONT> procedure takes time <I>O</I>(<I>n</I> lg <I>n</I>), since the call to <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> takes time <I>O(n</I>) and each of the <I>n</I> - 1 calls to <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> takes time <I>O</I>(lg <I>n</I>).<P>
<img src="148_a.gif"><P>
<h4><a name="076c_1321">Figure 7.4 The operation of <FONT FACE="Courier New" SIZE=2>HEAPSORT</FONT>. (a) The heap data structure just after it has been built by <FONT FACE="Courier New" SIZE=2>BUILD<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT></FONT></FONT>. (b)-(j) The heap just after each call of <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT> in line 5. The value of i at that time is shown. Only lightly shaded nodes remain in the heap. (k) The resulting sorted array A.<a name="076c_1321"></sub></sup></h4><P>





<h2><a name="076d_0001">Exercises<a name="076d_0001"></h2><P>
<a name="076d_0002">7.4-1<a name="076d_0002"><P>
Using Figure 7.4 as a model, illustrate the operation of <FONT FACE="Courier New" SIZE=2>HEAPSORT</FONT> on the array A = <img src="../images/lftwdchv.gif">5, 13, 2, 25, 7, 17, 20, 8, 4<img src="../images/wdrtchv.gif">.<P>
<a name="076d_0003">7.4-2<a name="076d_0003"><P>
What is the running time of heapsort on an array <I>A</I> of length <I>n</I> that is already sorted in increasing order? What about decreasing order?<P>
<a name="076d_0004">7.4-3<a name="076d_0004"><P>
Show that the running time of heapsort is <img src="../images/omega12.gif">(<I>n </I>lg <I>n</I>).<P>
<P>


<P>







<h1><a name="076e_1330">7.5 Priority queues<a name="076e_1330"></h1><P>
<a name="076e_1320"><a name="076e_1321"><a name="076e_1322"><a name="076e_1323">Heapsort is an excellent algorithm, but a good implementation of quicksort, presented in Chapter 8, usually beats it in practice. Nevertheless, the heap data structure itself has enormous utility. In this section, we present one of the most popular applications of a heap: its use as an efficient priority queue.<P>