NAME¶

std::ranges::sort_heap - std::ranges::sort_heap

Synopsis¶

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> (1) (since C++20)
constexpr I

sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );
template< ranges::random_access_range R, class Comp =
ranges::less,

class Proj = std::identity > (2) (since C++20)
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>

sort_heap( R&& r, Comp comp = {}, Proj proj = {} );

Converts the max heap [first, last) into a sorted range in ascending order. The
resulting range no longer has the heap property.

1) Elements are compared using the given binary comparison function comp and
projection object proj.
2) Same as (1), but uses 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 cannot be specified when calling any of them.
* None of them are visible to argument-dependent lookup.
* When any of them are found by normal unqualified lookup as the name to the left
of the function-call operator, argument-dependent lookup is inhibited.

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], and q = f[i], for all 0 < i < N, the
expression std::invoke(comp, std::invoke(proj, p), std::invoke(proj, q))
evaluates to false.
* 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¶

// Run this code

#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¶

ranges::is_heap checks if the given range is a max heap
(C++20) (niebloid)
ranges::is_heap_until finds the largest subrange that is a max heap
(C++20) (niebloid)
ranges::make_heap creates a max heap out of a range of elements
(C++20) (niebloid)
ranges::pop_heap removes the largest element from a max heap
(C++20) (niebloid)
ranges::push_heap adds an element to a max heap
(C++20) (niebloid)
turns a max heap into a range of elements sorted in ascending
sort_heap order
(function template)