.\" ident @(#)pop_heap.3
.\" Standard Template Library
.\" $$RW_INSERT_HEADER "slyrs.man"
.TH pop_heap 3C++ "02 Apr 1998" "Rogue Wave Software" "-"
.ce2
Standard C++ Library   
Copyright 1998, Rogue Wave Software, Inc.   

.SH NAME

\f2pop_heap\fP

\ - Moves the largest element off the heap.



.SH  SYNOPSIS


.RE
.RS 0
template <class RandomAccessIterator>
.RE
.RS 1
void
.RE
.RS 2
pop_heap(RandomAccessIterator first,
.RE
.RS 10
RandomAccessIterator last);
.RE
.RS 0

.br
template <class RandomAccessIterator, class Compare>
.RE
.RS 1
void
.RE
.RS 2
pop_heap(RandomAccessIterator first,
.RE
.RS 10
RandomAccessIterator last, Compare comp);



.SH  DESCRIPTION


A heap is a particular organization of elements in a range between two random access iterators\f2 [a, b)\fP. Its two key properties are:


.HP .5i
1.	\f2*a\fP is the largest element in the range.
.HP .5i
2.	\f2*a\fP may be removed by the pop_heap algorithm or a new element may be added by the push_heap algorithm, in \f2O(logN)\fP time.
.HP 0

These properties make heaps useful as priority queues.

The pop_heap algorithm uses the less than (\f2<\fP) operator as the default comparison. An alternate comparison operator can be specified.

The pop_heap algorithm can be used as part of an operation to remove the largest element from a heap. It assumes that the range \f2[first, last)\fP is a valid heap (in other words, that \f2first\fP is the largest element in the heap or the first element based on the alternate comparison operator). It then swaps the value in the location \f2first\fP with the value in the location \f2last - 1\fP and makes the range \f2[first, last  -1)\fPback into a heap. You can then access the element in \f2last\fP using the vector or deque \f2back()\fP member function, or you can remove the element using the \f2pop_back\fP member function. Note that pop_heap does not actually remove the element from the data structure; you must use another function to do that. 



.SH  COMPLEXITY


pop_heap performs at most \f22 * log(last - first)\fP comparisons.



.SH  EXAMPLE



.RE
.RS 0
//
.br
// heap_ops.cpp
.br
//
.RE
.RS 1
#include <algorithm>
.br
#include <vector>
.br
#include <iostream>
.RE
.RS 0
using namespace std;
.br

.br
int main(void)
.RE
.RS 1
{
.RE
.RS 2
int d1[4] = {1,2,3,4};
.br
int d2[4] = {1,3,2,4};               
.RE
.RS 0

.RE
.RS 3
// Set up two vectors
.RE
.RS 2
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);
.RE
.RS 0

.RE
.RS 3
// Make heaps
.RE
.RS 2
make_heap(v1.begin(),v1.end());
.br
make_heap(v2.begin(),v2.end(),less<int>());
.RE
.RS 3
// v1 = (4,x,y,z)  and  v2 = (4,x,y,z)
.br
// Note that x, y and z represent the remaining
.br
// values in the container (other than 4). 
.br
// The definition of the heap and heap operations 
.br
// does not require any particular ordering
.br
// of these values.
.RE
.RS 0

.RE
.RS 3
// Copy both vectors to cout
.RE
.RS 2
ostream_iterator<int,char> out(cout," ");
.br
copy(v1.begin(),v1.end(),out);
.br
cout << endl;
.br
copy(v2.begin(),v2.end(),out);
.br
cout << endl;
.RE
.RS 0

.RE
.RS 3
// Now let's pop
.RE
.RS 0
   pop_heap(v1.begin(),v1.end());
.RE
.RS 3
pop_heap(v2.begin(),v2.end(),less<int>());
.br
// v1 = (3,x,y,4) and v2 = (3,x,y,4)
.RE
.RS 0

.RE
.RS 3
// Copy both vectors to cout
.RE
.RS 2
copy(v1.begin(),v1.end(),out);
.br
cout << endl;
.br
copy(v2.begin(),v2.end(),out);
.br
cout << endl;
.RE
.RS 3

.br
// And push
.RE
.RS 2
push_heap(v1.begin(),v1.end());
.br
push_heap(v2.begin(),v2.end(),less<int>());
.RE
.RS 3
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
.RE
.RS 0

.RE
.RS 3
// Copy both vectors to cout
.RE
.RS 2
copy(v1.begin(),v1.end(),out);
.br
cout << endl;
.br
copy(v2.begin(),v2.end(),out);
.br
cout << endl;
.RE
.RS 0

.RE
.RS 3
// Now sort those heaps
.RE
.RS 2
sort_heap(v1.begin(),v1.end());
.br
sort_heap(v2.begin(),v2.end(),less<int>());
.RE
.RS 3
// v1 = v2 = (1,2,3,4)
.RE
.RS 6

.RE
.RS 3
// Copy both vectors to cout
.RE
.RS 2
copy(v1.begin(),v1.end(),out);
.br
cout << endl;
.br
copy(v2.begin(),v2.end(),out);
.br
cout << endl;
.RE
.RS 0

.RE
.RS 2
return 0;
.RE
.RS 1
}

.br
.RE
.RS 0
Program Output



.RE
.RS 0

.br
4 2 3 1
.br
4 3 2 1
.br
3 2 1 4
.br
3 1 2 4
.br
4 3 1 2
.br
4 3 2 1
.br
1 2 3 4
.br
1 2 3 4



.SH  WARNINGS


If your compiler does not support default template parameters, you always need to supply the \f2Allocator\fP template argument. For instance, you need to write:

\f2vector<int, allocator<int> >\fP

instead of:

\f2vector<int>\fP

If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP.



.SH  SEE ALSO


make_heap, push_heap, sort_heap