std::ranges::sort_heap

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
(C++11)(C++11)(C++11)
(C++17)
Modifying sequence operations
Partitioning operations
Sorting operations
(C++11)
Binary search operations
Set operations (on sorted ranges)
Heap operations
(C++11)
Minimum/maximum operations
(C++11)
(C++17)

Permutations
Numeric operations
Operations on uninitialized storage
(C++17)
(C++17)
(C++17)
C library
 
Constrained algorithms
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations
Set operations (on sorted ranges)
Heap operations
ranges::sort_heap
Minimum/maximum operations
Permutations
Constrained numeric operations
Fold operations
Operations on uninitialized storage
Return types
 
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.

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 2Nlog(N) comparisons and 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 𝓞(log N) time.
  • The first element can be removed using ranges::pop_heap, in 𝓞(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

checks if the given range is a max heap
(niebloid)
finds the largest subrange that is a max heap
(niebloid)
creates a max heap out of a range of elements
(niebloid)
removes the largest element from a max heap
(niebloid)
adds an element to a max heap
(niebloid)
turns a max heap into a range of elements sorted in ascending order
(function template)