Starting with the heap [ first...(last - 1 )), insert the element referenced by last into the heap [ first...(last - 1 )] so that [ first ... last ) is a heap. The first version uses operator< to perform comparisons, whereas the second version uses the binary function compare .

Declaration


  
#include <algorithm>

template< class RandomAccessIterator >
void push_heap
  (
  RandomAccessIterator first,
  RandomAccessIterator last
  );

template< class RandomAccessIterator, class Compare >
void push_heap
  (
  RandomAccessIterator first,
  RandomAccessIterator last,
  Compare compare
  );

Complexity

Time complexity is O(log(N)), where N is the size of the heap. Space complexity is constant.

Example <ospace/osstd/examples/pheap1.cpp>


    #include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v;
  v.push_back ( 1 );
  v.push_back ( 20 );
  v.push_back ( 4 );
  make_heap( v.begin(), v.end() );
  v.push_back ( 7 );

  push_heap( v.begin(), v.end() );

  sort_heap( v.begin(), v.end() );
  ostream_iterator< int > iter( cout, " " );
  copy( v.begin(), v.end(), iter );
  cout << "\n";
  }

1 4 20
1 4 7 20

Examples <ospace/osstd/examples/pheap2.cpp>


    #include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v;
  v.push_back ( 1 );
  v.push_back ( 20 );
  v.push_back ( 4 );
  make_heap( v.begin(), v.end(), greater< int >() );
  v.push_back ( 7 );

  push_heap( v.begin(), v.end(), greater< int >() );

  sort_heap( v.begin(), v.end(), greater< int >() );
  ostream_iterator< int > iter( cout, " " );
  copy( v.begin(), v.end(), iter );
  cout << "\n";
  }

20 7 4 1

push_heap

Library

Declaration

Complexity

Example <ospace/osstd/examples/pheap1.cpp>

Examples <ospace/osstd/examples/pheap2.cpp>