page361.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 94 行
HTML
94 行
<HTML>
<HEAD>
<TITLE>Removing Items from a Binary Heap</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html6385" HREF="page362.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page362.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6383" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6379" HREF="page360.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page360.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6387" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6388" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0012240000000000000000">Removing Items from a Binary Heap</A></H2>
<P>
The <tt>DequeueMin</tt> function removes from a priority queue
the 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 related to <tt>FindMin</tt>.
<P>
The smallest item is always at the root of a min heap.
Therefore, the <tt>FindMin</tt> operation is trivial.
Program <A HREF="page361.html#progbinheap3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page361.html#progbinheap3c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the code for the <tt>FindMin</tt>
member function of the <tt>BinaryHeap</tt> class.
Assuming that no exception is thrown,
the running time of <tt>FindMin</tt> is clearly <I>O</I>(1).
<P>
<P><A NAME="25307"> </A><A NAME="progbinheap3c"> </A> <IMG WIDTH=575 HEIGHT=124 ALIGN=BOTTOM ALT="program25237" SRC="img1470.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1470.gif" ><BR>
<STRONG>Program:</STRONG> <tt>BinaryHeap</tt> Class <tt>FindMin</tt> Member Function Definition<BR>
<P>
<P>
Since the bottom row of a complete tree is filled from left to right
as items are added,
it follows that the bottom row must be emptied from right to left
as 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="page361.html#figheap3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page361.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 tree
to make it into a complete tree again.
When key 2 is removed from the root, a hole is created in the tree
as shown in Figure <A HREF="page361.html#figheap3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page361.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (b).
<P>
<P><A NAME="25633"> </A><A NAME="figheap3"> </A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure25250" SRC="img1471.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1471.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 where
the 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 pushed
down to a leaf node,
or until the hole has been pushed to a point where the left over key
can be inserted into the heap.
In the example shown in Figure <A HREF="page361.html#figheap3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page361.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (b)-(c),
the hole is pushed from the root node to a leaf node
where the key 6 is ultimately placed is shown in Figure <A HREF="page361.html#figheap3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page361.html#figheap3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (d).
<P>
Program <A HREF="page361.html#progbinheap4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page361.html#progbinheap4c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the code for the <tt>DequeueMin</tt>
function of the <tt>BinaryHeap</tt> class.
This function implements the deletion algorithm described above.
The main loop (lines 9-19) moves the hole in the tree down
by moving up the child with the smallest key
until either a leaf node is reached
or until the hole has been moved down to a point where
the last element of the array can be reinserted.
<P>
<P><A NAME="25746"> </A><A NAME="progbinheap4c"> </A> <IMG WIDTH=575 HEIGHT=429 ALIGN=BOTTOM ALT="program25641" SRC="img1472.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1472.gif" ><BR>
<STRONG>Program:</STRONG> <tt>BinaryHeap</tt> Class <tt>DequeueMin</tt> Member Function Definition<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 comparisons
and moves the hole down one level.
Therefore, the running time of the <tt>DequeueMin</tt> operation is
<P> <IMG WIDTH=383 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath66402" SRC="img1473.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1473.gif" ><P>
where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61308" SRC="img709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img709.gif" > is the number of items in the heap
and the <IMG WIDTH=125 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline64816" SRC="img1293.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1293.gif" > is the time required to compare two object instances.
If
<P> <IMG WIDTH=341 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath66383" SRC="img1469.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1469.gif" ><P>
the <tt>DequeueMin</tt> operation is simply <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" > in the worst case.
<P>
<HR><A NAME="tex2html6385" HREF="page362.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page362.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6383" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6379" HREF="page360.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page360.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6387" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6388" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?