page370.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 88 行
HTML
88 行
<HTML><HEAD><TITLE>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="tex2html5452" HREF="page371.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5450" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5444" HREF="page369.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5454" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011420000000000000000">Binomial Queues</A></H2><P>If binomial trees only come in sizes that are powers of two,how do we implement a container which holds an arbitrary number numberof items <I>n</I> using binomial trees?The answer is related to the binary representation of the number <I>n</I>.Every non-negative integer <I>n</I> can be expressed in binary form as<P><A NAME="eqnpqueuesn"> </A> <IMG WIDTH=500 HEIGHT=49 ALIGN=BOTTOM ALT="equation26590" SRC="img1483.gif" ><P>where <IMG WIDTH=69 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66201" SRC="img1484.gif" > is the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" ><em>binary digit</em><A NAME=26597> </A><A NAME=26598> </A>or <em>bit</em><A NAME=26600> </A> in the representation of <I>n</I>.For example, <I>n</I>=27 is expressed as the binary number <IMG WIDTH=46 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66209" SRC="img1485.gif" > because 27=16+8+2+1.<P>To make a container which holds exactly <I>n</I> itemswe use a collection of binomial trees.A collection of trees is called a <em>forest</em><A NAME=26602> </A>.The forest contains binomial tree <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66215" SRC="img1486.gif" > if the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > bitin the binary representation of <I>n</I> is a one.That is, the forest <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59871" SRC="img470.gif" > which contains exactly <I>n</I> items is given by<P> <IMG WIDTH=316 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66193" SRC="img1487.gif" ><P>where <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66225" SRC="img1488.gif" > is determined from Equation <A HREF="page370.html#eqnpqueuesn"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.For example, the forest which contains 27 items is <IMG WIDTH=162 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66227" SRC="img1489.gif" ><P>The analogy between <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59871" SRC="img470.gif" > and the binary representation of <I>n</I>carries over to the merge operation.Suppose we have two forests,say <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59871" SRC="img470.gif" > and <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66235" SRC="img1490.gif" >.Since <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59871" SRC="img470.gif" > contains <I>n</I> items and <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66235" SRC="img1490.gif" > contains <I>m</I> items,the combination of the two contains <I>n</I>+<I>m</I> items.Therefore, the resulting forest is <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66247" SRC="img1491.gif" >.<P>For example, consider <I>n</I>=27 and <I>m</I>=10.In this case, we need to merge <IMG WIDTH=158 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66253" SRC="img1492.gif" > with <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66255" SRC="img1493.gif" >.Recall that two binomial trees of order <I>k</I> can be combinedto obtain a binomial tree of order <I>k</I>+1.For example, <IMG WIDTH=97 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66261" SRC="img1494.gif" >.But this is just like adding binary digits!In binary notation, the sum 27+10 is calculated like this:<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=7 BORDER RULES=GROUPS><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>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</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>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><P> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD></TR></TBODY></TABLE><BR> </P></DIV>The merging of <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66267" SRC="img1495.gif" > and <IMG WIDTH=22 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66269" SRC="img1496.gif" > is done in the same way:<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>Therefore, the result is <IMG WIDTH=132 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66309" SRC="img1501.gif" >.<P><HR><A NAME="tex2html5452" HREF="page371.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5450" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5444" HREF="page369.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5454" 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 + -
显示快捷键?