page365.html

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

HTML
91 行
字号 
<HTML><HEAD><TITLE>Merging Leftist Heaps</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="tex2html5393" HREF="page366.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5391" HREF="page361.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5385" HREF="page364.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5395" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011330000000000000000">Merging Leftist Heaps</A></H2><P>In order to merge two leftist heaps, say <tt>h1</tt> and <tt>h2</tt>,declared as follows<PRE>h1 = LeftistHeap()h2 = LeftistHeap()</PRE>we invoke the <tt>merge</tt> method like this:<PRE>h1.merge(h2)</PRE>The effect of the <tt>merge</tt> method is to take all the nodes from <tt>h2</tt>and to attach them to <tt>h1</tt>,thus leaving <tt>h2</tt> as the empty heap.<P>In order to achieve a logarithmic running time,it is important for the <tt>merge</tt> method to do all its workon the right sides of <tt>h1</tt> and <tt>h2</tt>.It turns out that the algorithm for merging leftist heapsis actually quite simple.<P>To begin with, if <tt>h1</tt> is the empty heap,then we can simply swap the contents of <tt>h1</tt> and <tt>h2</tt>.Otherwise, let us assume that the root of <tt>h2</tt> is larger thanthe root of <tt>h1</tt>.Then we can merge the two heaps by recursively merging <tt>h2</tt>with the <em>right</em> subheap of <tt>h1</tt>.After doing so, it may turn out that the right subheap of <tt>h1</tt>now has a larger null path length than the left subheap.This we rectify by swapping the left and right subheaps so that the resultis again leftist.On the other hand, if <tt>h2</tt> initially has the smaller root,we simply exchange the roles of <tt>h1</tt> and <tt>h2</tt> and proceed as above.<P>Figure&nbsp;<A HREF="page365.html#figleftist2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the merge operation.In this example, we wish to merge the two trees  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  > and  <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif"  >shown in Figure&nbsp;<A HREF="page365.html#figleftist2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>&nbsp;(a).Since  <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif"  > has the larger root,it is recursively merged with the right subtree of  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  >.The result of that merge replaces the right subtree of  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  >as shown in Figure&nbsp;<A HREF="page365.html#figleftist2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>&nbsp;(b).Since the null path length of the right subtree is now greater than the left,the subtrees of  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  > are swapped giving the leftist heapshown in Figure&nbsp;<A HREF="page365.html#figleftist2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>&nbsp;(c).<P><P><A NAME="25928">&#160;</A><A NAME="figleftist2">&#160;</A> <IMG WIDTH=575 HEIGHT=673 ALIGN=BOTTOM ALT="figure25556" SRC="img1432.gif"  ><BR><STRONG>Figure:</STRONG> Merging leftist heaps.<BR><P><P>Program&nbsp;<A HREF="page365.html#progleftistHeapb"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the <tt>merge</tt>method of the <tt>LeftistHeap</tt> class.The <tt>merge</tt> method makes use of two other methods,<tt>swapContentsWith</tt> and <tt>swapSubtrees</tt>.In addition to <tt>self</tt>,the <tt>swapContentsWith</tt> method takes as its argument a leftist heap,and exchanges all the contents (key and subtrees)of the <tt>self</tt> heap with the given one.The <tt>swapSubtrees</tt> method exchanges the left and right subtreesof a leftist heap.The implementation of these routines is trivial and is left as a projectfor the reader (Project&nbsp;<A HREF="page385.html#projectpqueuesleftist"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).Clearly, the worst-case running time for each of these routines is <I>O</I>(1).<P>The <tt>merge</tt> method only visits nodes on the rightmost pathsof the trees being merged.Suppose we are merging two trees, say  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  > and  <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif"  >,with null path lengths  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65895" SRC="img1433.gif"  > and  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65897" SRC="img1434.gif"  >, respectively.Then the running time of the <tt>Merge</tt> method is<P> <IMG WIDTH=382 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65871" SRC="img1435.gif"  ><P>where  <IMG WIDTH=53 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65775" SRC="img1413.gif"  > is time required to compare two keys.If we assume that the time to compare two keys is a constant,then we get  <IMG WIDTH=122 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65901" SRC="img1436.gif"  >,where  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58699" SRC="img269.gif"  > and  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58701" SRC="img270.gif"  > are the number of internal nodes intrees  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  > and  <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif"  >, respectively.<P><P><A NAME="26074">&#160;</A><A NAME="progleftistHeapb">&#160;</A> <IMG WIDTH=575 HEIGHT=332 ALIGN=BOTTOM ALT="program25946" SRC="img1437.gif"  ><BR><STRONG>Program:</STRONG> <tt>LeftistHeap</tt> class <tt>merge</tt> method.<BR><P><HR><A NAME="tex2html5393" HREF="page366.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5391" HREF="page361.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5385" HREF="page364.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5395" 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>

page365.html - 源码说明

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

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

⌨️ 快捷键说明

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