Przejdź do głównej zawartości

std::ranges::make_heap() algorithm

// (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>

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 9

max-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 3

min-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
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::make_heap() algorithm

// (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>

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 9

max-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 3

min-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
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.