Re: removing any element in a heap

On Thu, 3 Sep 2009 18:07:04 CST, Marc <marc.gli...@gmail.com> wrote:


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