📄 page352.html
字号:
<HTML><HEAD><TITLE>Basics</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="tex2html5245" HREF="page353.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5243" HREF="page351.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5237" HREF="page351.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5247" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0011100000000000000000">Basics</A></H1><P>A priority queue is a container which provides the following three operations:<DL ><DT><STRONG><tt>enqueue</tt></STRONG><DD> used to put objects into the container; <DT><STRONG><tt>min</tt></STRONG><DD> accesses the smallest object in the container; and <DT><STRONG><tt>dequeueMin</tt></STRONG><DD> removes the smallest object from the container.<P> </DL>A priority queue is used to store a finite set of keysdrawn from a totally ordered set of keys <I>K</I>.As distinct from search trees,duplicate keys <em>are</em> allowed in priority queues.<P>Program <A HREF="page352.html#progpriorityQueuea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>PriorityQueue</tt> class.The abstract <tt>PriorityQueue</tt> class extendsthe abstract <tt>Container</tt> class defined in Program <A HREF="page119.html#progcontainera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In addition to the inherited methods,the <tt>PriorityQueue</tt> class supportsthe three operations listed above.<P><P><A NAME="23470"> </A><A NAME="progpriorityQueuea"> </A> <IMG WIDTH=575 HEIGHT=374 ALIGN=BOTTOM ALT="program23385" SRC="img1374.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>PriorityQueue</tt> class.<BR><P><P>Program <A HREF="page352.html#progmergeablePriorityQueuea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the<tt>MergeablePriorityQueue</tt> class.The abstract <tt>MergeablePriorityQueue</tt> class extendsthe abstract <tt>PriorityQueue</tt> class defined in Program <A HREF="page352.html#progpriorityQueuea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.A <em>mergeable priority queue</em><A NAME=23408> </A><A NAME=23409> </A>is one which provides the ability tomerge efficiently two priority queues into one.Of course it is always possible to merge two priority queuesby dequeuing the elements of one queueand enqueueing them in the other.However, the mergeable priority queue implementations we will considerallow more efficient merging than this.<P><P><A NAME="23477"> </A><A NAME="progmergeablePriorityQueuea"> </A> <IMG WIDTH=575 HEIGHT=164 ALIGN=BOTTOM ALT="program23410" SRC="img1375.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>MergeablePriorityQueue</tt> class.<BR><P><P>It is possible to implement the required functionalityusing data structures that we have already considered.For example, a priority queue can be implemented simply as a list.If an <em>unsorted list</em><A NAME=23422> </A> is used,enqueueing can be accomplished in constant time.However, finding the minimum and removing the minimum each require <I>O</I>(<I>n</I>) timewhere <I>n</I> is the number of items in the queue.On the other hand,if a <em>sorted list</em><A NAME=23424> </A> is used,finding the minimum and removing it is easy--both operations can be done in constant time.However, enqueueing an item in a sorted list requires <I>O</I>(<I>n</I>) time.<P>Another possibility is to use a search tree.For example, if an <em>AVL tree</em><A NAME=23426> </A> is usedto implement a priority queue,then all three operations can be done in <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" > time.However, search trees provide more functionality than we need.Search trees support finding the largest item with <tt>max</tt>,deletion of arbitrary objects with <tt>withdraw</tt>,and the ability to visit in order all the contained objectsvia <tt>depthFirstTraversal</tt>.All these operations can be done as efficientlyas the priority queue operations.Because search trees support more methodsthan we really need for priority queues,it is reasonable to suspect that there are more efficient waysto implement priority queues.And indeed there are!<P>A number of different priority queue implementationsare described in this chapter.All the implementations have one thing in common--they are all based on a special kind of tree called a <em>min heap</em>or simply a <em>heap</em>.<P><BLOCKQUOTE> <b>Definition ((Min) Heap)</b><A NAME="defnheap"> </A>A <em>(Min) Heap</em><A NAME=23436> </A><A NAME=23437> </A> is a tree,<P> <IMG WIDTH=352 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65491" SRC="img1376.gif" ><P>with the following properties:<OL><LI> Every subtree of <I>T</I> is a heap; and,<LI> The root of <I>T</I> is less than or equal to the root of every subtree of <I>T</I>. That is, <IMG WIDTH=50 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline65509" SRC="img1377.gif" > for all <I>i</I>, <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62043" SRC="img895.gif" >, where <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65515" SRC="img1378.gif" > is the root of <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" >.</OL></BLOCKQUOTE>According to Definition <A HREF="page352.html#defnheap"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the key in each node of a heap is less than or equalto the roots of all the subtrees of that node.Therefore, by induction,the key in each node is less than or equal to all the keyscontained in the subtrees of that node.Note, however, that the definition says nothing about the relativeordering of the keys in the subtrees of a given node.For example, in a binary heap either the left or the right subtreeof a given node may have the larger key.<P><HR><A NAME="tex2html5245" HREF="page353.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5243" HREF="page351.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5237" HREF="page351.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5247" 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 + -