chap07.htm

介绍算法的书籍

<a name="076e_1324">A <I><B>priority queue</I></B> is a data structure for maintaining a set <I>S</I> of elements, each with an associated value called a <I><B>key</I></B>. A priority queue supports the following operations.<P>
<a name="076e_1325"><FONT FACE="Courier New" SIZE=2>INSERT</FONT>(<I>S</I>, <I>x</I>) inserts the element <I>x </I>into the set <I>S</I>. This operation could be written as <I>S </I><img src="../images/arrlt12.gif"> <I>S </I><img src="../images/wideu.gif"><I> {</I>x<I>}.</I><P>
<a name="076e_1326"><FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>(<I>S</I>) returns the element of<I> S </I>with the largest key.<P>
<a name="076e_1327"><FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT>(<I>S</I>) removes and returns the element of <I>S</I> with the largest key.<P>
One application of priority queues is to schedule jobs on a shared computer. The priority queue keeps track of the jobs to be performed and their relative priorities. When a job is finished or interrupted, the highest-priority job is selected from those pending using <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT>. A new job can be added to the queue at any time using <FONT FACE="Courier New" SIZE=2>INSERT</FONT>.<P>
A priority queue can also be used in an event-driven simulator. The items in the queue are events to be simulated, each with an associated time of occurrence that serves as its key. The events must be simulated in order of their time of occurrence, because the simulation of an event can cause other events to be simulated in the future. For this application, it is natural to reverse the linear order of the priority queue and support the operations <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> and <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> instead of <FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT> and <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT>. The simulation program uses <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> at each step to choose the next event to simulate. As new events are produced, they are inserted into the priority queue using <FONT FACE="Courier New" SIZE=2>INSERT</FONT>.<P>
<a name="076e_1328"><a name="076e_1329"><a name="076e_132a"><a name="076e_132b"><a name="076e_132c">Not surprisingly, we can use a heap to implement a priority queue. The operation <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT> returns the maximum heap element in <img src="../images/bound.gif">(1) time by simply returning the value <I>A</I>[1] in the heap. The <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT> procedure is similar to the <B>for</B> loop body (lines 3-5) of the <FONT FACE="Courier New" SIZE=2>HEAPSORT</FONT> procedure:<P>
<pre>HEAP-EXTRACT-MAX(<I>A</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>heap-size</I>[<I>A</I>] &lt; 1</sub></sup></pre><P>
<pre>2     <B>then error</B> "heap underflow"</sub></sup></pre><P>
<pre>3  <I>max</I> <img src="../images/arrlt12.gif"> <I>A</I>[1]</sub></sup></pre><P>
<pre>4  <I>A</I>[1] <img src="../images/arrlt12.gif"> <I>A</I>[<I>heap-size</I>[<I>A</I>]]</sub></sup></pre><P>
<pre>5  <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>6  HEAPIFY(<I>A</I>, 1)</sub></sup></pre><P>
<pre>7  <B>return</B> <I>max</I></sub></sup></pre><P>
The running time of <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT> is <I>O</I>(lg <I>n</I>), since it performs only a constant amount of work on top of the<I> O</I>(lg <I>n</I>) time for <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT>.<P>
<a name="076e_132d"><a name="076e_132e"><a name="076e_132f">The <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure inserts a node into heap <I>A</I>. To do so, it first expands the heap by adding a new leaf to the tree. Then, in a manner reminiscent of the insertion loop (lines 5-7) of <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> from Section 1.1, it traverses a path from this leaf toward the root to find a proper place for the new element.<P>
<pre>HEAP-INSERT(<I>A</I>,<I>key</I>)</sub></sup></pre><P>
<pre>1  <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>2  i <img src="../images/arrlt12.gif"> <I>heap-size</I>[<I>A</I>]</sub></sup></pre><P>
<pre>3  <B>while</B><I> i</I> &gt; 1 and <I>A</I>[PARENT(<I>i</I>)] &lt; <I>key</I></sub></sup></pre><P>
<pre>4      <B>do</B> <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> <I>A</I>[PARENT(<I>i</I>)]</sub></sup></pre><P>
<pre>5         <I>i </I><img src="../images/arrlt12.gif"> PARENT(<I>i</I>)</sub></sup></pre><P>
<pre>6  <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> <I>key</I></sub></sup></pre><P>
Figure 7.5 shows an example of a <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation. The running time of <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> on an <I>n</I>-element heap is <I>O</I>(lg <I>n</I>), since the path traced from the new leaf to the root has length<I> O</I>(lg <I>n</I>).<P>
In summary, a heap can support any priority-queue operation on a set of size <I>n</I> in<I> O</I>(lg <I>n</I>) time.<P>





<h2><a name="076f_1335">Exercises<a name="076f_1335"></h2><P>
<a name="076f_1336">7.5-1<a name="076f_1336"><P>
Using Figure 7.5 as a model, illustrate the operation of <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>(<I>A</I>, 3) on the heap <I>A</I> = <img src="../images/lftwdchv.gif">15,13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1<img src="../images/wdrtchv.gif">.<P>
<a name="076f_1337">7.5-2<a name="076f_1337"><P>
Illustrate the operation of <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT> on the heap <I>A</I> = <img src="../images/lftwdchv.gif">15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1<img src="../images/wdrtchv.gif">.<P>
<img src="151_a.gif"><P>
<h4><a name="076f_1338">Figure 7.5 The operation of <FONT FACE="Courier New" SIZE=2>HEAP<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>INSERT<FONT FACE="Times New Roman" SIZE=2>. (a) The heap of Figure 7.4(a) before we insert a node with key 15. (b) A new leaf is added to the tree. (c) Values on the path from the new leaf to the root are copied down until a place for the key 15 is found. (d) The key 15 is inserted.<a name="076f_1338"></FONT></FONT></FONT></FONT></sub></sup></h4><P>
<a name="076f_1339">7.5-3<a name="076f_1339"><P>
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (FIFO's and stacks are defined in Section 11.1.)<P>
<a name="076f_133a">7.5-4<a name="076f_133a"><P>
<a name="076f_1330"><a name="076f_1331"><a name="076f_1332">Give an <I>O</I>(lg <I>n</I>)-time implementation of the procedure <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INCREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>(<I>A, i, k</I>), which sets <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> max(<I>A</I>[<I>i</I>],<I>k</I>) and updates the heap structure appropriately.<P>
<a name="076f_133b">7.5-5<a name="076f_133b"><P>
<a name="076f_1333">The operation <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>(<I>A, i</I>) deletes the item in node<I> i</I> from heap <I>A</I>. Give an implementation of <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> that runs in <I>O</I>(lg <I>n</I>) time for an <I>n</I>-element heap.<P>
<a name="076f_133c">7.5-6<a name="076f_133c"><P>
<a name="076f_1334">Give an <I>O(n </I>lg <I>k</I>)-time algorithm to merge<I> k </I>sorted lists into one sorted list, where<I> n</I> is the total number of elements in all the input lists. (<I>Hint</I>: Use a heap for <I>k</I>-way merging.)<P>
<P>


<P>







<h1><a name="0770_133d">Problems<a name="0770_133d"></h1><P>
<a name="0770_133e">7-1     Building a heap using insertion<a name="0770_133e"><P>
<a name="0770_1335"><a name="0770_1336"><a name="0770_1337">The procedure <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> in Section 7.3 can be implemented by repeatedly using <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> to insert the elements into the heap. Consider the following implementation:<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"> 1</sub></sup></pre><P>
<pre>2  <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 2 <B>to</B> <I>length</I>[<I>A</I>]</sub></sup></pre><P>
<pre>3        <B>do</B> HEAP-INSERT(<I>A, A</I>[<I>i</I>])</sub></sup></pre><P>
<I><B>a</I>.</B>     Do the procedures <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> and <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP'</FONT> always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.<P>
<I><B>b</I>.     </B>Show that in the worst case, <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>' requires <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>) time to build an <I>n</I>-element heap.<P>
<a name="0770_133f">7-2     Analysis of d-ary heaps<a name="0770_133f"><P>
<a name="0770_1338"><a name="0770_1339">A <I><B>d-ary</I></B> <I><B>heap</I></B> is like a binary heap, but instead of 2 children, nodes have <I>d</I> children.<P>
<I><B>a</I></B><I>.     </I>How would you represent a <I>d</I>-ary heap in an array?<P>
<a name="0770_133a"><I><B>b</I></B><I>.     </I>What is the height of a <I>d</I>-ary heap of <I>n</I> elements in terms of <I>n</I> and <I>d</I>?<P>
<a name="0770_133b"><I><B>c</I></B><I>.     </I>Give an efficient implementation of <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT>. Analyze its running time in terms of <I>d</I> and <I>n</I>.<P>
<a name="0770_133c"><I><B>d</I></B><I>.     </I>Give an efficient implementation of <FONT FACE="Courier New" SIZE=2>INSERT</FONT>. Analyze its running time in terms of <I>d</I> and <I>n</I>.<P>
<I><B>e.     </I></B>Give an efficient implementation of <FONT FACE="Courier New" SIZE=2>HEAP</FONT>-<FONT FACE="Courier New" SIZE=2>INCREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>(<I>A, i, k</I>), which sets <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> max(<I>A</I>[<I>i</I>], <I>k</I>) and updates the heap structure appropriately. Analyze its running time in terms of <I>d</I> and<I> n</I>.<P>
<P>







<h1>Chapter notes</h1><P>
The heapsort algorithm was invented by Williams [202], who also described how to implement a priority queue with a heap. The <FONT FACE="Courier New" SIZE=2>BUILD</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> procedure was suggested by Floyd [69].<P>
<P>


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


</BODY></HTML>