Re: removing any element in a heap
On Thu, 3 Sep 2009 18:07:04 CST, Marc <marc.glisse@gmail.com> wrote:
On Sep 3, 7:25 am, George Neuner <gneun...@comcast.net> wrote:
On Wed, 2 Sep 2009 07:10:24 CST, Marc <marc.gli...@gmail.com> wrote:
I notice that the heap operations allow adding elements and removing
the maximum, but they don't allow removing some arbitrary element
(indicated by an iterator).
pop_heap is badly named but it does remove any element.
From the description athttp://www.cplusplus.com
[...]
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.
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
George
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]