std::pop_heap

default (1)	template <class RandomAccessIterator> void pop_heap (RandomAccessIterator first, RandomAccessIterator last);
custom (2)	template <class RandomAccessIterator, class Compare> void pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

default (1)

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

custom (2)

template <class RandomAccessIterator, class Compare>  void pop_heap (RandomAccessIterator first, RandomAccessIterator last,                 Compare comp);

Pop element from heap range

Rearranges the elements in the heap range [first,last) in such a way that the part considered a heap is shortened by one: The element with the highest value is moved to (last-1).

While the element with the highest value is moved from first to (last-1) (which now is out of the heap), the other elements are reorganized in such a way that the range [first,last-1) preserves the properties of a heap.

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 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.
This shall not be an empty range.
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 a 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.

Return value

none

Example

// 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 twice logarithmic in the distance between first and last: Compares elements and potentially swaps (or moves) them until rearranged as a shorter 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.