page359.html

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

HTML
78 行
字号 
<HTML><HEAD><TITLE>Putting Items into a Binary Heap</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="tex2html5325" HREF="page360.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5323" HREF="page353.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5317" HREF="page358.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5327" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011230000000000000000">Putting Items into a Binary Heap</A></H2><P>There are two requirements which must be satisfied whenan item is inserted in a binary heap.First, the resulting tree must have the correct shape.Second, the tree must remain heap-ordered.Figure&nbsp;<A HREF="page359.html#figheap2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the way in which this is done.<P>Since the resulting tree must be a complete tree,there is only one place in the tree where a node can be added.That is, since the bottom level must be filled from left to right,the node node must be added at the next available position in the bottomlevel of the tree as shown in Figure&nbsp;<A HREF="page359.html#figheap2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>&nbsp;(a).<P><P><A NAME="24615">&#160;</A><A NAME="figheap2">&#160;</A> <IMG WIDTH=575 HEIGHT=320 ALIGN=BOTTOM ALT="figure24310" SRC="img1409.gif"  ><BR><STRONG>Figure:</STRONG> Inserting an item into a binary heap.<BR><P><P>In this example, the new item to be inserted has the key&nbsp;2.Note that we cannot simply drop the new item into the next positionin the complete tree because the resulting tree is no longer heap ordered.Instead, the hole in the heap is moved toward the rootby moving items down in the heapas shown in Figure&nbsp;<A HREF="page359.html#figheap2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>&nbsp;(b) and&nbsp;(c).The process of moving items down terminates either when we reach the rootof the tree or when the hole has been moved up to a position in whichwhen the new item is inserted the result is a heap.<P>Program&nbsp;<A HREF="page359.html#progbinaryHeapb"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for inserting an itemin a binary heap.In addition to <tt>self</tt>,the <tt>enqueue</tt> method of the <tt>BinaryHeap</tt> classtakes as its argument the item to be inserted in the heap.If the priority queue is full an exception is thrown.Otherwise, the item is inserted as described above.<P><P><A NAME="24714">&#160;</A><A NAME="progbinaryHeapb">&#160;</A> <IMG WIDTH=575 HEIGHT=256 ALIGN=BOTTOM ALT="program24623" SRC="img1410.gif"  ><BR><STRONG>Program:</STRONG> <tt>BinaryHeap</tt> class <tt>enqueue</tt> method.<BR><P><P>The implementation of the algorithm is actually remarkably simple.Lines&nbsp;7-10 move the hole in the heap up by moving items down.When the loop terminates, the new item can be inserted at position <I>i</I>.Therefore, the loop terminates either at the root, <I>i</I>=1,or when the key in the parent of <I>i</I>,which is found at position  <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65723" SRC="img1403.gif"  >,is smaller than the item to be inserted.<P>Notice too thatthe subscript calculations involve only division by two.Therefore, the divisions can be replaced by bitwise right shiftswhich usually run much more quickly.<P>Since the depth of a complete binary tree with <I>n</I>nodes is  <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65773" SRC="img1411.gif"  >,the worst case running time for the <tt>enqueue</tt> operation is<P> <IMG WIDTH=343 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65761" SRC="img1412.gif"  ><P>where  <IMG WIDTH=53 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65775" SRC="img1413.gif"  > is the time required to compare to objects.If  <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65777" SRC="img1414.gif"  >,the <tt>enqueue</tt> operation is simply  <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif"  > in the worst case.<P><HR><A NAME="tex2html5325" HREF="page360.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5323" HREF="page353.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5317" HREF="page358.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5327" 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>

page359.html - 源码说明

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

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

⌨️ 快捷键说明

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