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

.SH NAME

\f2push_heap\fP

\ - Places a new element into a heap.



.SH  SYNOPSIS


.RE
.RS 0
#include <algorithm>
.br
template <class RandomAccessIterator>
.RE
.RS 1
void
.RE
.RS 2
push_heap(RandomAccessIterator first,
.RE
.RS 11
RandomAccessIterator last);
.RE
.RS 0

.br
template <class RandomAccessIterator, class Compare>
.RE
.RS 1
void
.RE
.RS 2
push_heap(RandomAccessIterator first,
.RE
.RS 11
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\f2 \fPalgorithm, 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 push_heap algorithms uses the less than (\f2<\fP) operator as the default comparison. As with all of the heap manipulation algorithms, an alternate comparison function can be specified.

The push_heap algorithm is used to add a new element to the heap. First, a new element for the heap is added to the end of a range. (For example, you can use the vector or deque member function \f2push_back()\fPto add the element to the end of either of those containers.) The push_heap algorithm assumes that the range \f2[first, last - 1)\fP is a valid heap. Then it properly positions the element in the location \f2last - 1\fP into its proper position in the heap, resulting in a heap over the range \f2[first, last)\fP.

Note that the push_heap algorithm does not place an element into the heap's underlying container. You must user another function to add the element to the end of the container before applying push_heap.



.SH  COMPLEXITY


For push_heap at most \f2log(last - first)\fP comparisons are performed.



.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 2
pop_heap(v1.begin(),v1.end());
.br
pop_heap(v2.begin(),v2.end(),less<int>());
.RE
.RS 3
// 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
.br
push_heap(v1.begin(),v1.end());
.RE
.RS 0
   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

.RE
.RS 0
// 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, pop_heap, sort_heap