page360.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 93 行
HTML
93 行
<HTML><HEAD><TITLE>Removing Items from 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="tex2html5334" HREF="page361.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5332" HREF="page353.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5328" HREF="page359.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5336" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011240000000000000000">Removing Items from a Binary Heap</A></H2><P>The <tt>dequeueMin</tt> method removes from a priority queuethe item having the smallest key.In order to remove the smallest item,it needs first to be located.Therefore, the <tt>dequeueMin</tt> operation is closely relatedto the <tt>getMin</tt> operation.<P>The smallest item is always at the root of a min heap.Therefore, the <tt>getMin</tt> operation is trivial.Program <A HREF="page360.html#progbinaryHeapc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the <tt>getMin</tt> methodof the <tt>BinaryHeap</tt> class.Assuming that no exception is thrown,the running time of <tt>getMin</tt> is clearly <I>O</I>(1).<P><P><A NAME="24716"> </A><A NAME="progbinaryHeapc"> </A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="program24646" SRC="img1415.gif" ><BR><STRONG>Program:</STRONG> <tt>BinaryHeap</tt> class <tt>getMin</tt> method.<BR><P><P>Since the bottom row of a complete tree is filled from left to rightas items are added,it follows that the bottom row must be emptied from right to leftas items are removed.So, we have a problem:The datum to be removed from the heap by <tt>dequeueMin</tt> is in the root,but the node to be removed from the heap is in the bottom row.<P>Figure <A HREF="page360.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a) illustrates the problem.The <tt>dequeueMin</tt> operation removes the key 2 from the heap,but it is the node containing key 6 that must be removed from the treeto make it into a complete tree again.When key 2 is removed from the root, a hole is created in the treeas shown in Figure <A HREF="page360.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).<P><P><A NAME="25042"> </A><A NAME="figheap3"> </A> <IMG WIDTH=575 HEIGHT=320 ALIGN=BOTTOM ALT="figure24659" SRC="img1416.gif" ><BR><STRONG>Figure:</STRONG> Removing an item from a binary heap.<BR><P><P>The trick is to move the hole down in the tree to a point wherethe left-over key, in this case the key 6,can be reinserted into the tree.To move a hole down in the tree,we consider the children of the empty node and move up the smallest key.Moving up the smallest key ensures that the result will be a min heap.<P>The process of moving up continues until either the hole has been pusheddown to a leaf node,or until the hole has been pushed to a point where the left over keycan be inserted into the heap.In the example shown in Figure <A HREF="page360.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b)-(c),the hole is pushed from the root node to a leaf nodewhere the key 6 is ultimately placed is shown in Figure <A HREF="page360.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d).<P>Program <A HREF="page360.html#progbinaryHeapd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the <tt>dequeueMin</tt>method of the <tt>BinaryHeap</tt> class.This method implements the deletion algorithm described above.The main loop (lines 10-18) moves the hole in the tree downby moving up the child with the smallest keyuntil either a leaf node is reachedor until the hole has been moved down to a point wherethe last element of the array can be reinserted.<P><P><A NAME="25159"> </A><A NAME="progbinaryHeapd"> </A> <IMG WIDTH=575 HEIGHT=428 ALIGN=BOTTOM ALT="program25050" SRC="img1417.gif" ><BR><STRONG>Program:</STRONG> <tt>BinaryHeap</tt> class <tt>dequeueMin</tt> method.<BR><P><P>In the worst case, the hole must be pushed from the root to a leaf node.Each iteration of the loop makes at most two object comparisonsand moves the hole down one level.Therefore, the running time of the <tt>dequeueMin</tt> operation is<P> <IMG WIDTH=386 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65781" SRC="img1418.gif" ><P>where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline60691" SRC="img663.gif" > is the number of items in the heap.If <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65787" SRC="img1419.gif" > and <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65789" SRC="img1420.gif" >,the <tt>dequeueMin</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="tex2html5334" HREF="page361.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5332" HREF="page353.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5328" HREF="page359.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5336" 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 + -
显示快捷键?