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)

Создаёт кучу относительно comp и proj из элементов указанного диапазона.

1) Указанный диапазон — [first, last).

2) Указанный диапазон — r.

Описанные на этой странице функциональные объекты, похожие на функции, являются функциональными объектами алгоритмов (неформально известными как niebloids), то есть:

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

Параметры

first, last	-	пара итератор–сентинел, задающая диапазон изменяемых элементов
r	-	`range` изменяемых элементов
comp	-	компаратор, применяемый к спроецированным элементам
proj	-	проекция, применяемая к элементам

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

1) last

2) ranges::end(r)

Сложность

Не более \(\scriptsize 3\cdot N\)3·N применений comp и \(\scriptsize 6\cdot N\)6·N применений proj, где \(\scriptsize N \)N — это:

1) ranges::distance(first, last)

2) ranges::distance(r)

Пример

#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, const auto& v)
{
    out(rem);
    for (auto e : v)
        out(e), out(' ');
    out('\n');
}

void draw_heap(const auto& 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)	проверяет, является ли заданный диапазон max-кучей (функциональный объект алгоритма)
ranges::is_heap_until (C++20)	находит наибольший поддиапазон, являющийся max-кучей (функциональный объект алгоритма)
ranges::push_heap (C++20)	добавляет элемент в max-кучу (функциональный объект алгоритма)
ranges::pop_heap (C++20)	удаляет наибольший элемент из max-кучи (функциональный объект алгоритма)
ranges::sort_heap (C++20)	преобразует max-кучу в отсортированный диапазон элементов (функциональный объект алгоритма)
make_heap	создаёт max-кучу из диапазона элементов (шаблон функции)

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