Login
pop_heap
Removes an element from a heap
Key Facts
Gyroscopic Couple: The rate of change of angular momentum (= Moment of Inertia.
= Angular velocity
= 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.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
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