page353.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 115 行
HTML
115 行
<HTML>
<HEAD>
<TITLE>Basics</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="tex2html6288" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.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="tex2html6286" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6280" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6290" 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="tex2html6291" 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="SECTION0012100000000000000000">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>FindMin</tt></STRONG>
<DD>
returns a reference to 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 keys
drawn 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="page353.html#progpqueue1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page353.html#progpqueue1h"><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> gives the declaration of the
<tt>PriorityQueue</tt> abstract class.
The <tt>PriorityQueue</tt> class is derived from the <tt>Container</tt> class.
In addition to the inherited functions,
the public interface of the <tt>PriorityQueue</tt> class comprises
the three functions listed above.
<P>
<P><A NAME="24052"> </A><A NAME="progpqueue1h"> </A> <IMG WIDTH=575 HEIGHT=391 ALIGN=BOTTOM ALT="program23974" SRC="img1428.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1428.gif" ><BR>
<STRONG>Program:</STRONG> <tt>PriorityQueue</tt> and <tt>MergeablePriorityQueue</tt> Class Definitions<BR>
<P>
<P>
Program <A HREF="page353.html#progpqueue1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page353.html#progpqueue1h"><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> also declares one additional class--<tt>MergeablePriorityQueue</tt>.
A <em>mergeable priority queue</em><A NAME=23994> </A><A NAME=23995> </A>
is one which provides the ability to
merge efficiently two priority queues into one.
Of course it is always possible to merge two priority queues
by dequeuing the elements of one queue
and enqueuing them in the other.
However, the mergeable priority queue implementations we will consider
allow more efficient merging than this.
<P>
<P><A NAME="24000"> </A><A NAME="figclasses7"> </A> <IMG WIDTH=575 HEIGHT=131 ALIGN=BOTTOM ALT="figure23996" SRC="img1429.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1429.gif" ><BR>
<STRONG>Figure:</STRONG> Object Class Hierarchy<BR>
<P>
<P>
It is possible to implement the required functionality
using 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=24004> </A> is used,
enqueuing can be accomplished in constant time.
However, finding the minimum and removing the minimum each require <I>O</I>(<I>n</I>) time
where <I>n</I> is the number of items in the queue.
On the other hand,
if an <em>sorted list</em><A NAME=24006> </A> is used,
finding the minimum and removing it is easy--both operations can be done in constant time.
However, enqueuing an item in an 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=24008> </A> is used
to implement a priority queue,
then all three operations can be done in <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" > time.
However, search trees provide more functionality than we need.
Viz., search trees support finding the largest item with <tt>FindMax</tt>,
deletion of arbitrary objects with <tt>Withdraw</tt>,
and the ability to visit in order all the contained objects
via <tt>DepthFirstTraversal</tt>.
All these operations can be done as efficiently
as the priority queue operations.
Because search trees support more functions
than we really need for priority queues,
it is reasonable to suspect that there are more efficient ways
to implement priority queues.
And indeed there are!
<P>
A number of different priority queue implementations
are 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=24018> </A><A NAME=24019> </A> is a tree,
<P> <IMG WIDTH=353 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66128" SRC="img1430.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1430.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>.
I.e., <IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66146" SRC="img1431.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1431.gif" >,
where <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66148" SRC="img1432.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1432.gif" > is the root of <IMG WIDTH=13 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63460" SRC="img1099.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1099.gif" >.
</OL></BLOCKQUOTE>
According to Definition <A HREF="page353.html#defnheap" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page353.html#defnheap"><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>,
the key in each node of a heap is less than or equal
to 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 keys
contained in the subtrees of that node.
Note, however, that the definition says nothing about the relative
ordering of the keys in the subtrees of a given node.
For example, in a binary heap either the left or the right subtree
of a given node may have the larger key.
<P>
<HR><A NAME="tex2html6288" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.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="tex2html6286" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6280" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6290" 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="tex2html6291" 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 + =
减小字号Ctrl + -
显示快捷键?