page501.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 90 行
HTML
90 行
<HTML><HEAD><TITLE>Implementation</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="tex2html6930" HREF="page502.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6928" HREF="page500.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6924" HREF="page500.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6932" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0015521000000000000000">Implementation</A></H3><P>In the first phase of heapsort,the unsorted array is transformed into a max heap.Throughout the process we view the array as a complete binary tree.Since the data in the array is initially unsorted,the tree is not initially heap-ordered.We make the tree into a max heap from the bottom up.That is, we start with the leaves and work towards the root.Figure <A HREF="page501.html#figpercolate"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates this process.<P><P><A NAME="39883"> </A><A NAME="figpercolate"> </A> <IMG WIDTH=575 HEIGHT=373 ALIGN=BOTTOM ALT="figure39083" SRC="img2070.gif" ><BR><STRONG>Figure:</STRONG> Combining heaps by percolating values.<BR><P><P>Figure <A HREF="page501.html#figpercolate"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a) shows a complete tree that is not yet heap ordered--the root is smaller than both its children.However, the two subtrees of the root <em>are</em> heap ordered.Given that both of the subtrees of the root are already heap ordered,we can heapify the tree by <em>percolating</em>the value in the root down the tree.<P>To percolate a value down the tree,we swap it with its largest child.For example, in Figure <A HREF="page501.html#figpercolate"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b) we swap 3 and 7.Swapping with the largest child ensures that after the swap,the new root is greater than or equal to <em>both</em> its children.<P>Notice that after the swap the heap-order is satisfied at the root,but not in the left subtree of the root.We continue percolating the 3 down by swapping it with 6as shown in Figure <A HREF="page501.html#figpercolate"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).In general, we percolate a value down either until it arrives ina position in which the heap order is satisfiedor until it arrives in a leaf.As shown in Figure <A HREF="page501.html#figpercolate"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d),the tree obtained when the percolation is finished is a max heap<P>Program <A HREF="page501.html#progheapSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <tt>HeapSorter</tt> class.The <tt>HeapSorter</tt> class extends the abstract <tt>Sorter</tt> classdefined in Program <A HREF="page481.html#progsortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>percolateDown</tt> method shown in Program <A HREF="page501.html#progheapSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>implements the algorithm described above.In addition to <tt>self</tt>,the <tt>percolateDown</tt> method takes two arguments:the number of elements in the array to be considered, <IMG WIDTH=82 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline60415" SRC="img585.gif" >,and the position, <I>i</I>, of the node to be percolated.<P><P><A NAME="40005"> </A><A NAME="progheapSortera"> </A> <IMG WIDTH=575 HEIGHT=371 ALIGN=BOTTOM ALT="program39903" SRC="img2071.gif" ><BR><STRONG>Program:</STRONG> <tt>HeapSorter</tt> class <tt>__init__</tt> and <tt>percolateDown</tt> methods.<BR><P><P>The purpose of the <tt>percolateDown</tt> methodis to transform the subtree rooted at position <I>i</I> into a max heap.It is assumed that the left and right subtrees of the nodeat position <I>i</I> are already max heaps.Recall that the children of node <I>i</I> are found at positions 2<I>i</I> and 2<I>i</I>+1.<tt>percolateDown</tt> percolates the value in position <I>i</I> down the treeby swapping elements until the value arrives in a leaf nodeor until both children of <I>i</I> contain smaller value.<P>A constant amount of work is done in each iteration.Therefore, the running time of the <tt>percolateDown</tt> methodis determined by the number of iterations of its main loop (lines 8-17).In fact, the number of iterations required in the worst caseis equal to the height in the tree of node <I>i</I>.<P>Since the root of the tree has the greatest height,the worst-case occurs for <I>i</I>=1.In Chapter <A HREF="page351.html#chappqueues"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> it is shown that the height of a complete binary treeis <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65773" SRC="img1411.gif" >.Therefore the worst-case running timeof the <tt>percolateDown</tt> method is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P><HR><A NAME="tex2html6930" HREF="page502.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6928" HREF="page500.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6924" HREF="page500.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6932" 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 + -
显示快捷键?