# push_heap

**Visual Studio 2010**

Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.

template<class RandomAccessIterator> void push_heap( RandomAccessIterator _First, RandomAccessIterator _Last ); template<class RandomAccessIterator, class BinaryPredicate> void push_heap( RandomAccessIterator _First, RandomAccessIterator _Last, BinaryPredicate _Comp );

The element must first be pushed back to the end of an existing heap and then the algorithm is used to add this element to the existing heap.

Heaps have two properties:

The first element is always the largest.

Elements may be added or removed in logarithmic time.

Heaps are an ideal way to implement priority queues and they are used in the implementation of the Standard Template Library container adaptor priority_queue Class.

The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.

The range excluding the newly added element at the end must be a heap.

The complexity is logarithmic, requiring at most log (*_Last – _First*) comparisons.

// alg_push_heap.cpp // compile with: /EHsc #include <vector> #include <algorithm> #include <functional> #include <iostream> int main( ) { using namespace std; vector <int> v1, v2; vector <int>::iterator Iter1, Iter2; int i; for ( i = 1 ; i <= 9 ; i++ ) v1.push_back( i ); random_shuffle( v1.begin( ), v1.end( ) ); cout << "Vector v1 is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; // Make v1 a heap with default less than ordering make_heap ( v1.begin( ), v1.end( ) ); cout << "The heaped version of vector v1 is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; // Add an element to the heap v1.push_back( 10 ); cout << "The heap v1 with 10 pushed back is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; push_heap( v1.begin( ), v1.end( ) ); cout << "The reheaped v1 with 10 added is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl << endl; // Make v1 a heap with greater than ordering make_heap ( v1.begin( ), v1.end( ), greater<int>( ) ); cout << "The greater-than heaped version of v1 is\n ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; v1.push_back(0); cout << "The greater-than heap v1 with 11 pushed back is\n ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; push_heap( v1.begin( ), v1.end( ), greater<int>( ) ); cout << "The greater than reheaped v1 with 11 added is\n ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; }

Vector v1 is ( 9 2 7 3 1 6 8 4 5 ). The heaped version of vector v1 is ( 9 5 8 4 1 6 7 2 3 ). The heap v1 with 10 pushed back is ( 9 5 8 4 1 6 7 2 3 10 ). The reheaped v1 with 10 added is ( 10 9 8 4 5 6 7 2 3 1 ). The greater-than heaped version of v1 is ( 1 2 6 3 5 8 7 4 10 9 ). The greater-than heap v1 with 11 pushed back is ( 1 2 6 3 5 8 7 4 10 9 0 ). The greater than reheaped v1 with 11 added is ( 0 1 6 3 2 8 7 4 10 9 5 ).