C++ Programming Code Examples
Learn C++ Language
Algorithm Library pop_heap() Function in C++ Programming Language
Algorithm Library pop_heap() Function in C++
Pop element from heap range. Rearranges the elements in the heap range [first,last) in such a way that the part considered a heap is shortened by one: The element with the highest value is moved to (last-1). pop_heap() function is used to delete the maximum element of the heap. The size of heap is decreased by 1. The heap elements are reorganised accordingly after this operation.
While the element with the highest value is moved from first to (last-1) (which now is out of the heap), the other elements are reorganized in such a way that the range [first,last-1) preserves the properties of a heap.
A range can be organized into a heap by calling make_heap. After that, its heap properties are preserved if elements are added and removed from it using push_heap and pop_heap, respectively.
Syntax for pop_heap() Function in C++
#include <algorithm>
//default (1)
template <class RandomAccessIterator>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last);
//custom (2)
template <class RandomAccessIterator, class Compare>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
first, last
Random-access iterators to the initial and final positions of the heap to be shrank by one. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. This shall not be an empty range.
comp
Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to be less than the second in the specific strict weak ordering it defines. Unless [first,last) is a one-element heap, this argument shall be the same as used to construct the heap.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.
This function does not return any value.
Complexity
Up to twice logarithmic in the distance between first and last: Compares elements and potentially swaps (or moves) them until rearranged as a shorter heap.
Data races
Some (or all) of the objects in the range [first,last) are modified.
Exceptions
Throws if any of the element comparisons, the element swaps (or moves) or the operations on iterators throws. Note that invalid arguments cause undefined behavior.
/* C++ Algorithm pop_heap() function is used to swap the value in the position ?first? and the value in the position ?last-1? and makes the sub range [first, last-1) into a max heap. It has the effect of removing the first (largest) element from the heap defined by the range [first, last). Elements are compared using operator < for the first version or using the given binary comparison function comp for the second version. */
/* Pop element from heap range by pop_heap() function code example */
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
v1.push_back( i );
// Make v1 a heap with default less than ordering
random_shuffle( v1.begin( ), v1.end( ) );
make_heap ( v1.begin( ), v1.end( ) );
cout << "The heaped version of vector v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Add an element to the back of the heap
v1.push_back( 10 );
push_heap( v1.begin( ), v1.end( ) );
cout << "The reheaped v1 with 10 added is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Remove the largest element from the heap
pop_heap( v1.begin( ), v1.end( ) );
cout << "The heap v1 with 10 removed is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl << endl;
// Make v1 a heap with greater-than ordering with a 0 element
make_heap ( v1.begin( ), v1.end( ), greater<int>( ) );
v1.push_back( 0 );
push_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The 'greater than' reheaped v1 puts the smallest "
<< "element first:\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Application of pop_heap to remove the smallest element
pop_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The 'greater than' heaped v1 with the smallest element\n "
<< "removed from the heap is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
return 0;
}
This C++ example uses a class that contains a constructor used to 'initialize the object'. The class is called ShoeBox. When supplied with a Length, a Height, a Width, the object should
