page378.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 49 行
HTML
49 行
<HTML>
<HEAD>
<TITLE>FindMinTree and FindMin Member Functions</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="tex2html6601" HREF="page379.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page379.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="tex2html6599" HREF="page373.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page373.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="tex2html6595" HREF="page377.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page377.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="tex2html6603" 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="tex2html6604" 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>
<H3><A NAME="SECTION0012435000000000000000"><tt>FindMinTree</tt> and <tt>FindMin</tt> Member Functions</A></H3>
<P>
A binomial queue that contains <I>n</I> items consists of
at most <IMG WIDTH=87 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66948" SRC="img1561.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1561.gif" > binomial trees.
Each of these binomial trees is heap ordered.
In particular, the smallest key in each binomial tree
is at the root of that tree.
So, we know that the smallest key in the queue
is found at the root of one of the binomial trees,
but we do not know which tree it is.
<P>
The private member function <tt>FindMinTree</tt> is used to determine
which of the binomial trees in the queue has the smallest root.
As shown in Program <A HREF="page378.html#progbinom3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page378.html#progbinom3c"><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 <tt>FindMinTree</tt> simply traverses the entire linked list
to find the tree with the smallest key at its root.
Since there are at most <IMG WIDTH=87 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66948" SRC="img1561.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1561.gif" > binomial trees,
the worst-case running time of <tt>FindMinTree</tt> is
<P> <IMG WIDTH=418 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath66952" SRC="img1562.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1562.gif" ><P>
<P>
<P><A NAME="27718"> </A><A NAME="progbinom3c"> </A> <IMG WIDTH=575 HEIGHT=391 ALIGN=BOTTOM ALT="program27543" SRC="img1563.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1563.gif" ><BR>
<STRONG>Program:</STRONG> <tt>BinomialQueue</tt> Class <tt>FindMinTree</tt> and <tt>FindMin</tt> Member Function Definitions<BR>
<P>
<P>
Program <A HREF="page378.html#progbinom3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page378.html#progbinom3c"><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 defines the public <tt>FindMin</tt> function
which returns the smallest key in the priority queue.
The <tt>FindMin</tt> function uses <tt>FindMinTree</tt> to locate the
tree with the smallest key at its root
and returns a reference to that key.
Clearly, the asymptotic running time of <tt>FindMin</tt> is the same
as that of <tt>FindMinTree</tt>.
<P>
<HR><A NAME="tex2html6601" HREF="page379.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page379.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="tex2html6599" HREF="page373.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page373.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="tex2html6595" HREF="page377.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page377.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="tex2html6603" 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="tex2html6604" 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 + -
显示快捷键?