page380.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 61 行
HTML
61 行
<HTML><HEAD><TITLE>Removing an Item from a Binomial Queue</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="tex2html5564" HREF="page381.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5562" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5558" HREF="page379.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5566" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011460000000000000000">Removing an Item from a Binomial Queue</A></H2><P>A binomial queue is a forest of heap-ordered binomial trees.Therefore, to dequeue the smallest item from the queue,we must withdraw the root of one of the binomial trees.But what do we do with the rest of the treeonce its root has been removed?<P>The solution lies in realizing that the collection ofsubtrees of the root of a binomial tree is a forest!For example, consider the binomial tree of order <I>k</I>,<P> <IMG WIDTH=361 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66429" SRC="img1518.gif" ><P>Taken all together, its subtrees form the binomial queue <IMG WIDTH=39 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline66439" SRC="img1519.gif" >:<P> <IMG WIDTH=362 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66430" SRC="img1520.gif" ><P><P>Therefore, to delete the smallest item from a binomial queue,we first identify the binomial tree with the smallest rootand remove that tree from the queue.Then, we consider all the subtrees of the root of that treeas a binomial queue and merge that queue back into the original one.Program <A HREF="page380.html#progbinomialQueueg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how this can be coded.<P><P><A NAME="27143"> </A><A NAME="progbinomialQueueg"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program27059" SRC="img1521.gif" ><BR><STRONG>Program:</STRONG> <tt>BinomialQueue</tt> class <tt>dequeueMin</tt> method.<BR><P><P>The <tt>dequeueMin</tt> method beginsby using the <tt>minTree</tt> accessor to find the tree with the smallest rootand then removing that tree using <tt>removeTree</tt> (lines 6-7).The time required to find the appropriate tree and to remove it is<P> <IMG WIDTH=382 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66431" SRC="img1522.gif" ><P>where <I>n</I> is the number of items in the queue.<P>A new binomial queue is created on line 8.All the children of the root of the minimum tree are detached from the tree and added to the new binomial queue (lines 9-12).In the worst case, the minimum tree is the one with the highest order.i.e., <IMG WIDTH=55 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline66443" SRC="img1523.gif" >,and the root of that tree has <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65773" SRC="img1411.gif" > children.Therefore, the running time of the loop on lines 9-12 is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P>The new queue is then merged with the original one (line 13).Since the resulting queue contains <I>n</I>-1 keys,the running time for the <tt>merge</tt> operation in this case is<P> <IMG WIDTH=343 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66432" SRC="img1524.gif" ><P><HR><A NAME="tex2html5564" HREF="page381.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5562" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5558" HREF="page379.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5566" 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 + =
减小字号Ctrl + -
显示快捷键?