std::ranges::make_heap

Определено в заголовке <algorithm>

Подпись вызова

Определено в заголовке `<algorithm>`
Подпись вызова
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 = {} );	(1)	(с 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> make_heap( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(с C++20)

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 = {} );

(1)

(с 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>
    make_heap( R&& r, Comp comp = {}, Proj proj = {} );

(2)

(с C++20)

Создаёт кучу максимального значения в диапазоне [first, last).

1) Элементы сравниваются с использованием заданной бинарной функции сравнения comp и объекта проекции proj.

2) То же, что и (1), но используется r как диапазон, как если бы ranges::begin(r) использовался как first и ranges::end(r) как last.

Функциональные сущности, описанные на этой странице, являются ниблоидами, то есть:

Явные списки шаблонов аргументов не могут быть указаны при вызове любого из них.
Ни один из них не виден для поиска аргументов по зависимостям (ADL).
Когда любой из них обнаруживается при обычном неквалифицированном поиске в качестве имени слева от оператора вызова функции, поиск аргументов по зависимостям (ADL) подавляется.

На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.

Параметры

first, last	-	диапазон элементов для создания кучи
r	-	диапазон элементов для создания кучи
pred	-	предикат для применения к спроецированным элементам
proj	-	проекция для применения к элементам

Возвращаемое значение

Итератор, равный last.

Сложность

Учитывая N = ranges::distance(first, last), не более \(\scriptsize 3\cdot N\)3•N сравнений и \(\scriptsize 6\cdot N\)6•N проекций.

Примечания

Куча максимального значения — это диапазон элементов [f, l), упорядоченных относительно компаратора comp и проекции proj, которые имеют следующие свойства:

С N = l - f, p = f[(i - 1) / 2], и q = f[i], для всех 0 < i < N, выражение std::invoke(comp, std::invoke(proj, p), std::invoke(proj, q)) вычисляется как false.
Новый элемент может быть добавлен с помощью ranges::push_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).
Первый элемент может быть удалён с помощью ranges::pop_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).

Пример

#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <vector>
 
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');
}
 
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());
}
 
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);
}

Вывод:

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

См. также

ranges::is_heap (C++20)	проверяет, является ли заданный диапазон кучей максимального значения (ниблоид)
ranges::is_heap_until (C++20)	находит самый большой поддиапазон, являющийся кучей максимального значения (ниблоид)
ranges::push_heap (C++20)	добавляет элемент в кучу максимального значения (ниблоид)
ranges::pop_heap (C++20)	удаляет наибольший элемент из кучи максимального значения (ниблоид)
ranges::sort_heap (C++20)	преобразует кучу максимального значения в диапазон элементов, отсортированных в порядке возрастания (ниблоид)
make_heap	создаёт кучу максимального значения из диапазона элементов (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/make_heap