function template
<algorithm>
std::push_heap
default (1) |
template <class RandomAccessIterator>
void push_heap (RandomAccessIterator first, RandomAccessIterator last);
|
---|
custom (2) |
template <class RandomAccessIterator, class Compare>
void push_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp); |
---|
Push element into heap range
Given a heap in the 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 within it.
A range can be organized into a heap by calling make_heap. After that, its heap properties are preserved if elements are added and removed from it using push_heap and pop_heap, respectively.
Parameters
- first, last
- Random-access iterators to the initial and final positions of the new heap range, 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
- Binary function that accepts two elements in the range as arguments, and returns a value convertible to
bool
. The value returned indicates whether the element passed as first argument is considered to be less than the second in the specific strict weak ordering it defines.
Unless [first,last)
is an empty or one-element heap, this argument shall be the same as used to construct the heap.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.
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
|
// range heap example
#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector
int main () {
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
std::cout << "initial max heap : " << v.front() << '\n';
std::pop_heap (v.begin(),v.end()); v.pop_back();
std::cout << "max heap after pop : " << v.front() << '\n';
v.push_back(99); std::push_heap (v.begin(),v.end());
std::cout << "max heap after push: " << v.front() << '\n';
std::sort_heap (v.begin(),v.end());
std::cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++)
std::cout << ' ' << v[i];
std::cout << '\n';
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
Up to logarithmic in the distance between first and last: Compares elements and potentially swaps (or moves) them until rearranged as a longer heap.
Data races
Some (or all) of the objects in the range [first,last)
are modified.
Exceptions
Throws if any of the element comparisons, the element swaps (or moves) or the operations on iterators throws.
Note that invalid arguments cause undefined behavior.
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
)