stdpop_heap(3)
std::pop_heap - std::pop_heap
Synopsis
Defined in header<algorithm>
template <class RandomIt>
(until C++ 20)
void pop_heap(RandomIt first, RandomIt last);
template <class RandomIt>
(since C++ 20)
constexpr void pop_heap(RandomIt first, RandomIt last);
(1)
template <class RandomIt, class Compare>
(until C++ 20)
void pop_heap(RandomIt first, RandomIt last, Compare comp);
(2)
template <class RandomIt, class Compare>
(since C++ 20)
constexpr void pop_heap(RandomIt first, RandomIt last, Compare comp);Swaps the value in the position first and the value in the position last-1 and makes the subrange [first, last-1) into a max heap. This has the effect of removing the first (largest) element from the heap defined by the range [first, last). The first version of the function uses operator< to compare the elements, the second uses the given comparison function comp.
Parameters
first, last - the range of elements defining the valid nonempty heap to modify
Type requirements
RandomIt must meet the requirements of ValueSwappable and LegacyRandomAccessIterator.
The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.
Return value
(none)
Complexity
At most 2×log(N) comparisons where N=std::distance(first, last).
Notes
A max heap is a range of elements [f,l) that has the following properties:
Example
// Run this code
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
std::cout << "v: ";
for (auto i : v)
std::cout << i << ’ ‘;
std::cout << ‘\n’;
std::pop_heap(v.begin(), v.end()); // moves the largest to the end
std::cout << "after pop_heap: ";
for (auto i : v)
std::cout << i << ’ ‘;
std::cout << ‘\n’;
int largest = v.back();
v.pop_back(); // actually removes the largest element
std::cout << "largest element: " << largest << ‘\n’;
std::cout << "heap without largest: ";
for (auto i : v)
std::cout << i << ’ ‘;
std::cout << ‘\n’;
}
Output:
See also