C++ <algorithm> - pop_heap() Function

The C++ algorithm::pop_heap function is used to swap the first element with the element at position (last-1) and then makes the subrange [first, last-1) into a max heap.

Syntax

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

//custom version 
template <class RandomAccessIterator, class Compare>
  void pop_heap(
     RandomAccessIterator first, 
     RandomAccessIterator last,
     BinaryPredicate comp
  );

Parameters

`first`	Specify initial position of the random-access iterator. The range used is [first,last).
`last`	Specify final position of the random-access iterator. The range used is [first,last).
`comp`	A binary predicate that takes two elements in the range as arguments and returns a bool. It follows the strict weak ordering to order the elements.

Return Value

None.

Time Complexity

Up to twice logarithmic in the distance between first and last i.e, Θ(2log(n)), where n is the distance between first and last.

Example:

In the example below, the algorithm::pop_heap function is used to reduce the max heap range by one and rearrange the subrange into max heap.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main (){
  vector<int> vec{10, 5, 55, 22, 27, -10};
  vector<int>::iterator it;

  cout<<"vec contains:";
  for(it = vec.begin(); it != vec.end(); ++it)
    cout<<" "<<*it;

  //make the vector max heap
  make_heap(vec.begin(), vec.end());

  cout<<"\nAfter make_heap call, vec contains:";
  for(it = vec.begin(); it != vec.end(); ++it)
    cout<<" "<<*it;

  //calling pop_heap function which moves
  //first(largest) element to the last and
  //rearrange the subrange into max heap
  pop_heap(vec.begin(), vec.end());

  cout<<"\nAfter pop_heap call, vec contains:";
  for(it = vec.begin(); it != vec.end(); ++it)
    cout<<" "<<*it;

  return 0;
}

The output of the above code will be:

vec contains: 10 5 55 22 27 -10
After make_heap call, vec contains: 55 27 10 22 5 -10
After pop_heap call, vec contains: 27 22 10 -10 5 55

❮ C++ <algorithm> Library