push_heap
function template
<algorithm>
template <class RandomAccessIterator>
void push_heap ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void push_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Push element into heap range
Given a heap range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location in it.
A range can be made into a heap by calling function make_heap. Once created, its heap properties can be preserved by using push_heap and pop_heap respectively to add and remove values from it.
Parameters
- first, last
- Random-Access iterators to the initial and final positions of the new heap, including the pushed element. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- comp
- Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.
Return value
none
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
// range heap example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;
make_heap (v.begin(),v.end());
cout << "initial max heap : " << v.front() << endl;
pop_heap (v.begin(),v.end()); v.pop_back();
cout << "max heap after pop : " << v.front() << endl;
v.push_back(99); push_heap (v.begin(),v.end());
cout << "max heap after push: " << v.front() << endl;
sort_heap (v.begin(),v.end());
cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
cout << endl;
return 0;
}
|
Output:
initial max heap : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99
|
Complexity
At most, log(last-first) comparisons.
See also
| make_heap | Make heap from range (function template) |
| pop_heap | Pop element from heap range (function template) |
| sort_heap | Sort elements of heap (function template) |
| reverse | Reverse range (function template) |
|