std::ranges::make_heap() algorithm

od C++20

Simplified

// (1)constexpr I    make_heap( I first, S last, Comp comp = {}, Proj proj = {} );// (2)constexpr ranges::borrowed_iterator_t<R>    make_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>

Detailed

// (1)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    make_heap( I first, S last, Comp comp = {}, Proj proj = {} );// (2)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>    make_heap( R&& r, Comp comp = {}, Proj proj = {} );

Constructs a max heap in the range [first; last).

• (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 3 * N comparisons and 6 * N projections.

Exceptions

(none)

Possible implementation

make_heap(1) and make_heap(2)

struct make_heap_fn{    template<std::random_access_iterator I, std::sentinel_for<I> S,             class Proj = std::identity, std::indirect_strict_weak_order<             std::projected<I, Proj>> Comp = ranges::less>    constexpr bool operator()(I first, S last, Comp comp = {}, Proj proj = {}) const    {        return (last == ranges::make_heap_until(first, last,                                              std::move(comp), std::move(proj)));    }    template<ranges::random_access_range R, class Proj = std::identity,             std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R>, Proj>>             Comp = ranges::less>    constexpr bool operator()(R&& r, Comp comp = {}, Proj proj = {}) const    {        return (*this)(ranges::begin(r), ranges::end(r),                       std::move(comp), std::move(proj));    }};inline constexpr make_heap_fn make_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 <cmath>#include <functional>#include <iostream>#include <vector>void draw_heap(auto const& v);void out(const auto& what, int n = 1){    while (n-- > 0)        std::cout << what;}void print(auto rem, auto const& v){    out(rem);    for (auto e : v)        out(e), out(' ');    out('\n');}int main(){    std::vector h {1, 6, 1, 8, 0, 3, 3, 9, 8, 8, 7, 4, 9, 8, 9};    print("source: ", h);    std::ranges::make_heap(h);    print("\n" "max-heap: ", h);    draw_heap(h);    std::ranges::make_heap(h, std::greater {});    print("\n" "min-heap: ", h);    draw_heap(h);}void draw_heap(auto const& v){    auto bails = [](int n, int w)    {        auto b = [](int w) { out("┌"), out("─", w), out("┴"), out("─", w), out("┐"); };        if (!(n /= 2))            return;        for (out(' ', w); n-- > 0; )            b(w), out(' ', w + w + 1);        out('\n');    };    auto data = [](int n, int w, auto& first, auto last)    {        for (out(' ', w); n-- > 0 && first != last; ++first)            out(*first), out(' ', w + w + 1);        out('\n');    };    auto tier = [&](int t, int m, auto& first, auto last)    {        const int n {1 << t};        const int w {(1 << (m - t - 1)) - 1};        bails(n, w), data(n, w, first, last);    };    const int m {static_cast<int>(std::ceil(std::log2(1 + v.size())))};    auto first {v.cbegin()};    for (int i {}; i != m; ++i)        tier(i, m, first, v.cend());}

Possible Output

source: 1 6 1 8 0 3 3 9 8 8 7 4 9 8 9max-heap: 9 8 9 8 8 4 9 6 1 0 7 1 3 8 3       9   ┌───┴───┐   8       9 ┌─┴─┐   ┌─┴─┐ 8   8   4   9┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐6 1 0 7 1 3 8 3min-heap: 0 1 1 8 6 3 3 9 8 8 7 4 9 8 9       0   ┌───┴───┐   1       1 ┌─┴─┐   ┌─┴─┐ 8   6   3   3┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐9 8 8 7 4 9 8 9