📄 page351.html
字号:
<HTML><HEAD><TITLE>Heaps and Priority Queues</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5227" HREF="page352.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5225" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5219" HREF="page350.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5229" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0011000000000000000000">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 itemsin which each item has associated with it a <em>priority</em>.In general, different items may have different prioritiesand 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 prioritiesstarting 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 printingmuch more quickly than it is possible to print them.A simple solution is to place the documentsin a <em>FIFO</em> queue (Chapter <A HREF="page130.html#chapstacks"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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 printingwill experience a long delay whenmuch longer documents are already in the queue.An alternative solution is to use a priority queue in whichthe 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 lengthminimizes the average time a user waits for his document.<P>Priority queues are often used in the implementation of algorithms.Typically the problem to be solved consists of a number of subtasksand the solution strategy involves prioritizing the subtasksand then performing those subtasks in the order of their priorities.For example,in Chapter <A HREF="page433.html#chapalgorithms"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we show how a priority queuecan improve the performance of backtracking algorithms,in Chapter <A HREF="page478.html#chapsorting"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we will see how a priority queue can be used in sortingand in Chapter <A HREF="page519.html#chapgraphs"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> several graph algorithms that use a priority queueare discussed.<P><BR> <HR><UL> <LI> <A NAME="tex2html5230" HREF="page352.html#SECTION0011100000000000000000">Basics</A><LI> <A NAME="tex2html5231" HREF="page353.html#SECTION0011200000000000000000">Binary Heaps</A><LI> <A NAME="tex2html5232" HREF="page361.html#SECTION0011300000000000000000">Leftist Heaps</A><LI> <A NAME="tex2html5233" HREF="page368.html#SECTION0011400000000000000000">Binomial Queues</A><LI> <A NAME="tex2html5234" HREF="page381.html#SECTION0011500000000000000000">Applications</A><LI> <A NAME="tex2html5235" HREF="page384.html#SECTION0011600000000000000000">Exercises</A><LI> <A NAME="tex2html5236" HREF="page385.html#SECTION0011700000000000000000">Projects</A></UL><HR><A NAME="tex2html5227" HREF="page352.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5225" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5219" HREF="page350.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5229" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -