Re: removing any element in a heap
On Sep 4, 10:01 pm, George Neuner <gneun...@comcast.net> wrote:
On Fri, 4 Sep 2009 17:20:38 CST, Marc <marc.gli...@gmail.com> wrote:
On Sep 4, 6:30 am, George Neuner <gneun...@comcast.net> wrote:
On Thu, 3 Sep 2009 18:07:04 CST, Marc <marc.gli...@gmail.com> wrote:
On Sep 3, 7:25 am, George Neuner <gneun...@comcast.net> wrote:
pop_heap is badly named but it does remove any element.
Er... So if I give you a heap (iterator first, iterator end) and an
element to remove (iterator target), what calls would you make
exactly?
The first argument to pop_heap is the target to remove. The target is
relocated to the end of the range and the remaining elements are
resorted to preserve the heap property. If you think of the heap as a
pile, pop_heap bubbles the target element to the top of the pile.
Assuming that the range [begin,end] is a heap and target is within the
range, you'd call
pop_heap( target, end )
After the call, (end-1) refers to the target element and the range
[begin .. (end-2)] remains heap sorted.
pop_heap has a precondition that [begin,end) is a heap, but [target,
end) is not necessarily a heap.
Correct, but pop_heap reorders the elements so that the heap property
remains when the target is removed from the range.
But the thing is, without begin, it is missing a crucial piece of
information. The children of a node n of the heap are defined as begin
+2*(n-begin)+1 (and +2), which requires begin. Without knowing what
the heap is, how could it maintain the heap property?
If you are really convinced it works, could you describe
algorithmically how the function can achieve this?
Ex:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector <int> A;
vector <int>::iterator t;
int i;
for( i = 0; i < 10; ++i )
A.push_back( i );
cout << "Before make_heap: ";
copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
cout << endl;
make_heap(A.begin(), A.end());
cout << "After make_heap : ";
copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
cout << endl;
/* find and pop '7' */
t = find( A.begin(), A.end(), 7 );
pop_heap( t, A.end() );
cout << "After pop : ";
copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
Before make_heap: 0 1 2 3 4 5 6 7 8 9
After make_heap : 9 8 6 7 4 5 2 0 3 1
After pop : 9 8 6 5 4 3 2 0 1 7
I added a random_shuffle to the initial vector:
Before make_heap: 4 9 5 3 0 6 7 8 2 1
After make_heap : 9 8 7 4 1 6 5 3 2 0
After pop : 9 8 4 6 1 0 5 3 2 7
(not a heap)
Just to be clear, following the call to pop_heap the last element (7)
is not part of the heap.
But you're right, the 5 in your result is out of order. It looks like
you might have a bug in your pop_heap (or sort_heap). I added random
shuffle as you did and ran it repeatedly ... I get a properly ordered
heap out every time.
Maybe the example is too small for your implementation to exhibit the
problem? With g++ (several releases from 3.3 to trunk), most
executions end up with a valid heap, only a few are like this one. Did
you try running pop_heap after manually creating the heap that fails
for me?
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]