std::ranges::sort_heap
Defined in header <algorithm> |
||
---|---|---|
Call signature | ||
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr I sort_heap( I first, S last, Comp comp = {}, Proj proj = {} ); |
(1) | (since C++20) |
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> sort_heap( R&& r, Comp comp = {}, Proj proj = {} ); |
(2) | (since C++20) |
Converts the max heap [first, last)
into a sorted range in ascending order. The resulting range no longer has the heap property.
comp
and projection object
proj
.
r
as the range, as if using
ranges::begin(r)
as
first
and
ranges::end(r)
as
last
.
The function-like entities described on this page are niebloids, that is:
- Explicit template argument lists may not be specified when calling any of them.
- None of them is visible to argument-dependent lookup.
- When one of them is found by normal unqualified lookup for the name to the left of the function-call operator, it inhibits argument-dependent lookup.
In practice, they may be implemented as function objects, or with special compiler extensions.
Parameters
first, last | - | the range of elements to sort |
r | - | the range of elements to sort |
pred | - | predicate to apply to the projected elements |
proj | - | projection to apply to the elements |
Return value
An iterator equal to last
.
Complexity
Given N = ranges::distance(first, last)
, at most \(\scriptsize 2N\log{(N)}\)2Nlog(N) comparisons and \(\scriptsize 4N\log{(N)}\)4Nlog(N) projections.
Notes
A max heap is a range of elements [f, l)
, arranged with respect to comparator comp
and projection proj
, that has the following properties:
- With
N = l-f
,p = f[(i-1)/2]
, andq = f[i]
, for all0 < i < N
, the expressionstd::invoke(comp, std::invoke(proj, p), std::invoke(proj, q))
evaluates tofalse
. - A new element can be added using
ranges::push_heap
, in \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N) time. - The first element can be removed using
ranges::pop_heap
, in \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N) time.
Possible implementation
struct sort_heap_fn { template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr I operator()( I first, S last, Comp comp = {}, Proj proj = {} ) const { auto ret {ranges::next(first, last)}; for (; first != last; --last) { ranges::pop_heap(first, last, comp, proj); } return ret; } template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()( R&& r, Comp comp = {}, Proj proj = {} ) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr sort_heap_fn sort_heap{}; |
Example
#include <algorithm> #include <array> #include <iostream> void print(auto const& rem, auto const& v) { std::cout << rem; for (const auto i : v) std::cout << i << ' '; std::cout << '\n'; } int main() { std::array v {3, 1, 4, 1, 5, 9}; print("original array: ", v); std::ranges::make_heap(v); print("after make_heap: ", v); std::ranges::sort_heap(v); print("after sort_heap: ", v); }
Output:
original array: 3 1 4 1 5 9 after make_heap: 9 5 4 1 1 3 after sort_heap: 1 1 3 4 5 9
See also
(C++20)
|
checks if the given range is a max heap (niebloid) |
(C++20)
|
finds the largest subrange that is a max heap (niebloid) |
(C++20)
|
creates a max heap out of a range of elements (niebloid) |
(C++20)
|
removes the largest element from a max heap (niebloid) |
(C++20)
|
adds an element to a max heap (niebloid) |
turns a max heap into a range of elements sorted in ascending order (function template) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/sort_heap