Recover Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttp://yahoo.com/
advanced search

Valid RSS

Computing › Stl › Algorithms › Heap ›

pop_heap

Removes an element from a heap
+ View version details
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. Page Comments

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.

References

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

See Also

Last Modified: 2012-01-07 19:04:31     Page Rendered: 2012-05-22 08:07:04
 

Page Comments

 
 Format Excel Equations

  You must login to leave a messge