📄 page352.html
字号:
<HTML>
<HEAD>
<TITLE>Heaps and Priority Queues</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html6269" HREF="page353.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page353.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6267" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6261" HREF="page351.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6271" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6272" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION0012000000000000000000">Heaps and Priority Queues</A></H1>
<P>
<A NAME="chappqueues"> </A>
<P>
In this chapter we consider priority queues.
A priority queue is essentially a list of items
in which each item has associated with it a <em>priority</em>.
In general, different items may have different priorities
and we speak of one item having a higher priority than another.
Given such a list we can determine which is the highest
(or the lowest) priority item in the list.
Items are inserted into a priority queue in any, arbitrary order.
However,
items are withdrawn from a priority queue in order of their priorities
starting with the highest priority item first.
<P>
For example,
consider the software which manages a printer.
In general, it is possible for users to submit documents for printing
much more quickly than it is possible to print them.
A simple solution is to place the documents
in a <em>FIFO</em> queue (Chapter <A HREF="page130.html#chapstacks" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page130.html#chapstacks"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
In a sense this is fair,
because the documents are printed on a first-come, first-served basis.
<P>
However,
a user who has submitted a short document for printing
will experience a long delay when
much longer documents are already in the queue.
An alternative solution is to use a priority queue in which
the shorter a document, the higher its priority.
By printing the shortest documents first,
we reduce the level of frustration experienced by the users.
In fact,
it can be shown that printing documents in order of their length
minimizes the average time a user waits for her document.
<P>
Priority queues are often used in the implementation of algorithms.
Typically the problem to be solved consists of a number of subtasks
and the solution strategy involves prioritizing the subtasks
and then performing those subtasks in the order of their priorities.
For example,
in Chapter <A HREF="page440.html#chapalgorithms" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page440.html#chapalgorithms"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> we show how a priority queue
can improve the performance of backtracking algorithms,
in Chapter <A HREF="page483.html#chapsorting" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page483.html#chapsorting"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> we will see how a priority queue can be used in sorting
and in Chapter <A HREF="page523.html#chapgraphs" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#chapgraphs"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> several graph algorithms that use a priority queue
are discussed.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html6273" HREF="page353.html#SECTION0012100000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page353.html#SECTION0012100000000000000000">Basics</A>
<LI> <A NAME="tex2html6274" HREF="page354.html#SECTION0012200000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.html#SECTION0012200000000000000000">Binary Heaps</A>
<LI> <A NAME="tex2html6275" HREF="page362.html#SECTION0012300000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page362.html#SECTION0012300000000000000000">Leftist Heaps</A>
<LI> <A NAME="tex2html6276" HREF="page370.html#SECTION0012400000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page370.html#SECTION0012400000000000000000">Binomial Queues</A>
<LI> <A NAME="tex2html6277" HREF="page382.html#SECTION0012500000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page382.html#SECTION0012500000000000000000">Applications</A>
<LI> <A NAME="tex2html6278" HREF="page385.html#SECTION0012600000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#SECTION0012600000000000000000">Exercises</A>
<LI> <A NAME="tex2html6279" HREF="page386.html#SECTION0012700000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page386.html#SECTION0012700000000000000000">Projects</A>
</UL>
<HR><A NAME="tex2html6269" HREF="page353.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page353.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6267" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6261" HREF="page351.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6271" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6272" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -