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)