pop_heap

10,000+ views

GPL — licence
Edit / fork this page
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. References
  7. See Also

Removes an element from a heap

Computing Stl Algorithms Heap

View versions (1)

Definition

The pop_heap() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class RandomAccessIterator >
   void pop_heap(
      RandomAccessIterator first, 
      RandomAccessIterator last
   );
template < class RandomAccessIterator, class BinaryPredicate >
   void pop_heap(
      RandomAccessIterator first, 
      RandomAccessIterator last,
      BinaryPredicate comp
   );

Parameters:

ParameterDescription
firstA random-access iterator addressing the position of the first element in the heap
lastA random-access iterator addressing the position one past the final element in the heap
compUser-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Pop_heap function removes first (largest) element from the heap defined by the range [first, last) by switching the value in the position first and the value in the position last-1 and makes the subrange [first, last-1) into a heap.

The first version compares objects using operator< and the second compares objects using a function object comp.

Return Value

None.

Complexity

Performs at most (2*log(last - first)) comparisons; logarithmic complexity.

References

Example 1
Problem

This program illustrates the use of the STL pop_heap() algorithm (default version) to delete the top (root) (highest priority) (largest) value from a (maximum) heap of integers.

Workings
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int a[] = {100, 19, 36, 17, 3, 25, 1, 2, 7};
  vector<int> v(a, a+9);

  cout <<"\nHere are the values in the vector (the heap):\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";

  cout <<"\nNow we delete (pop) a value from the heap.";
  pop_heap(v.begin(), v.end());
  
  cout <<"\nHere are the revised contents of the vector:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
   cout <<v.at(i)<<" ";
  cout <<"\nNote that the value deleted from the heap is still "
         "\nin the vector (at the end of the vector).";

  cout <<"\nSo, we should reduce the size of the vector by 1, which "
         "we now do, and\nthen display the vector, which is once again a heap, one more time.";

  v.resize(v.size()-1);
  cout <<"\nHere are the final contents of the vector:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";

  return 0;
}
Solution

Output:

Here are the values in the vector (the heap):
100 19 36 17 3 25 1 2 7

Now we delete (pop) a value from the heap.

Here are the revised contents of the vector:
36 19 25 17 3 7 1 2 100
Note that the value deleted from the heap is still
in the vector (at the end of the vector).

So, we should reduce the size of the vector by 1, which we now do, and
then display the vector, which is once again a heap, one more time.

Here are the final contents of the vector:
36 19 25 17 3 7 1 2

References

See Also