W3cubDocs

/C++

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 [firstlast) 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:

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 [fl), 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

#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