page378.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 82 行

HTML
82 行
字号 
<HTML><HEAD><TITLE>Merging Binomial 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="tex2html5544" HREF="page379.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5542" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5536" HREF="page377.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5546" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011440000000000000000">Merging Binomial Queues</A></H2><P>Merging two binomial queues is like doing binary addition.For example, consider the addition of  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66267" SRC="img1495.gif"  > and  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66293" SRC="img1497.gif"  >:<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=8 BORDER RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>	   </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65981" SRC="img1451.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66117" SRC="img1467.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66267" SRC="img1495.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 	+</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>     </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66117" SRC="img1467.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66293" SRC="img1497.gif"  > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><P>	   </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66295" SRC="img1498.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66301" SRC="img1499.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=22 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66307" SRC="img1500.gif"  > </TD></TR></TBODY></TABLE></P></DIV>The usual algorithm for addition begins with the least-significant ``bit.''Since  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66267" SRC="img1495.gif"  > contains a  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif"  > tree and  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66293" SRC="img1497.gif"  > does not,the result is simply the  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif"  > tree from  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66267" SRC="img1495.gif"  >.<P>In the next step,we add the  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif"  > from  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66267" SRC="img1495.gif"  > and the  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif"  > from  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66293" SRC="img1497.gif"  >.Combining the two  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif"  >s we get a  <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66301" SRC="img1499.gif"  > which we <em>carry</em><A NAME=27000>&#160;</A>to the next column.Since there are no  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif"  >s left,the result does not contain any.The addition continues in a similar manneruntil all the columns have been added up.<P>Program&nbsp;<A HREF="page378.html#progbinomialQueued"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an implementation of this addition algorithm.In addition to <tt>self</tt>,the <tt>merge</tt> method of the <tt>BinomialQueue</tt> classtakes a <tt>BinomialQueue</tt> and adds its subtreesto the binomial queue <tt>self</tt>.<P><P><A NAME="27135">&#160;</A><A NAME="progbinomialQueued">&#160;</A> <IMG WIDTH=575 HEIGHT=600 ALIGN=BOTTOM ALT="program27007" SRC="img1511.gif"  ><BR><STRONG>Program:</STRONG> <tt>BinomialQueue</tt> class <tt>merge</tt> method.<BR><P><P>Each iteration of the main loop of the algorithm (lines&nbsp;11-28)computes the  <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif"  > ``bit'' of the result--the  <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif"  > bit is a binomial tree of order <I>i</I>.At most three terms need to be considered:the carry from the preceding iteration and two  <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66215" SRC="img1486.gif"  >s,one from each of the queues that are being merged.<P>The method <tt>fullAdder</tt>computes the result required in each iteration.Program&nbsp;<A HREF="page378.html#progbinomialQueuee"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines <tt>fullAdder</tt> method.In the worst case,the <tt>fullAdder</tt> method calls the <tt>add</tt> methodto combine two <tt>BinomialTree</tt>s into one.Therefore, the worst-case running time for <tt>fullAdder</tt> is<P> <IMG WIDTH=304 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66337" SRC="img1512.gif"  ><P><P><P><A NAME="27139">&#160;</A><A NAME="progbinomialQueuee">&#160;</A> <IMG WIDTH=575 HEIGHT=543 ALIGN=BOTTOM ALT="program27026" SRC="img1513.gif"  ><BR><STRONG>Program:</STRONG> <tt>BinomialQueue</tt> class <tt>fullAdder</tt> method.<BR><P><P>Suppose the <tt>merge</tt> method of Program&nbsp;<A HREF="page378.html#progbinomialQueued"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> isused to combine a binomial queue with <I>n</I> items with anotherthat contains <I>m</I> items.Since the resulting priority queue contains <I>n</I>+<I>m</I> items,there are at most  <IMG WIDTH=119 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66421" SRC="img1514.gif"  > binomial trees in the result.Thus, the worst-case running time for the <tt>merge</tt> operation is<P> <IMG WIDTH=400 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66338" SRC="img1515.gif"  ><P><HR><A NAME="tex2html5544" HREF="page379.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5542" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5536" HREF="page377.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5546" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page378.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page378.html 源码文件，采用 HTML 编程语言编写，共 82 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?