Przejdź do głównej zawartości

std::ranges::sort_heap() algorithm

// (1)
constexpr I
sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
sort_heap( R&& r, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::random_access_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::random_access_range
  • Comp - (none)
  • Proj - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

Additionally, each overload has the following constraints:

  • (1) - std::sortable<I, Comp, Proj>
  • (2) - std::sortable<ranges::iterator_t<R>, Comp, 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 source 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.

Parameters

first
last

The range of elements to make a heap from.

r

The range of elements to make a heap from.

pred

Predicate to apply to the projected elements.

proj

The projection to apply to the elements.

Return value

An iterator equal to last.

Complexity

Given N as ranges::distance(first, last):

At most 2 * N * log(N) comparisons and 4 * N * log(N) projections.

Exceptions

(none)

Possible implementation

sort_heap(1) and sort_heap(2)
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 {};

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:

  • Given N as 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 O(log(N)) time.
  • The first element can be removed using ranges::pop_heap, in O(log(N)) time.

Examples

Main.cpp
#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);
}
Possible 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::sort_heap() algorithm

// (1)
constexpr I
sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
sort_heap( R&& r, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::random_access_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::random_access_range
  • Comp - (none)
  • Proj - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

Additionally, each overload has the following constraints:

  • (1) - std::sortable<I, Comp, Proj>
  • (2) - std::sortable<ranges::iterator_t<R>, Comp, 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 source 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.

Parameters

first
last

The range of elements to make a heap from.

r

The range of elements to make a heap from.

pred

Predicate to apply to the projected elements.

proj

The projection to apply to the elements.

Return value

An iterator equal to last.

Complexity

Given N as ranges::distance(first, last):

At most 2 * N * log(N) comparisons and 4 * N * log(N) projections.

Exceptions

(none)

Possible implementation

sort_heap(1) and sort_heap(2)
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 {};

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:

  • Given N as 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 O(log(N)) time.
  • The first element can be removed using ranges::pop_heap, in O(log(N)) time.

Examples

Main.cpp
#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);
}
Possible 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.