pop_heap
function template
<algorithm>
template <class RandomAccessIterator>
void pop_heap ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void pop_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Pop element from heap range
Rearranges the elements in the range [first,last) in such a way that the part considered a heap is shortened by one by removing its highest element.
The function actually moves the value at first to (last-1), and adjusts the values of the elements in the range [first,last-1) so that this part of the range retains the heap property (with its first element being the new highest value).
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 heap to be shrank by one. 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, (2*log(last-first)) comparisons.
See also
| make_heap | Make heap from range (function template) |
| push_heap | Push element into heap range (function template) |
| sort_heap | Sort elements of heap (function template) |
| reverse | Reverse range (function template) |
|