I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
ComputingStlAlgorithmsHeap

pop_heap

Removes an element from a heap
+ View version details

Key Facts

Gyroscopic Couple: The rate of change of angular momentum (\inline \tau) = \inline I\omega\Omega (In the limit).
  • \inline I = Moment of Inertia.
  • \inline \omega = Angular velocity
  • \inline \Omega = Angular velocity of precession.


Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.

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:
Parameter Description
first A random-access iterator addressing the position of the first element in the heap
last A random-access iterator addressing the position one past the final element in the heap
comp User-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.
Example:
Example - pop_heap algorithm
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