stdsort_heap(3)
std::sort_heap - std::sort_heap
Synopsis
Defined in header<algorithm>
template <class RandomIt>
(until C++ 20)
void sort_heap(RandomIt first, RandomIt last);
template <class RandomIt>
(since C++ 20)
constexpr void sort_heap(RandomIt first, RandomIt last);
(1)
template <class RandomIt, class Compare>
(until C++ 20)
void sort_heap(RandomIt first, RandomIt last, Compare comp);
(2)
template <class RandomIt, class Compare>
(since C++ 20)
constexpr void sort_heap(RandomIt first, RandomIt last, Compare comp);Converts the max heap [first, last) into a sorted range in ascending order. The resulting range no longer has the heap property. 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 to sort
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×N×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: Defect reports The following behavior-changing defect reports were applied retroactively to previously published C++ standards. DR Applied to Behavior as published Correct behavior LWG_2444 C++98 complexity requirement was wrong by a factor of 2 corrected
Possible implementation
First version
Second version
Example
// Run this code
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
std::vector<int> v = {3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
std::cout << "heap:\t";
for (const auto &i : v) {
std::cout << i << ’ ‘;
}
std::sort_heap(v.begin(), v.end());
std::cout << "\nsorted:\t";
for (const auto &i : v) {
std::cout << i << ’ ‘;
}
std::cout << ‘\n’;
}
Output:
See also