Namespaces
Variants

std::ranges::push_heap

От ru.cppreference.net
 
 
Библиотека алгоритмов
Ограниченные алгоритмы и алгоритмы над диапазонами (C++20)
Ограниченные алгоритмы, например, ranges::copy, ranges::sort, ...
Немодифицирующие операции последовательности    
Пакетные операции
(C++17)
Операции поиска
Модифицирующие операции последовательности
Операции копирования
(C++11)
(C++11)
Операции обмена
Операции преобразования
Операции генерации
Операции удаления
Операции изменения порядка
(до C++17)(C++11)
(C++20)(C++20)
Операции выборки
(C++17)

Сортировка и связанные операции
Операции разделения
(C++11)    

Операции сортировки
Операции двоичного поиска
(на разделённых диапазонах)
Операции над множествами (на отсортированных диапазонах)
Операции слияния (на отсортированных диапазонах)
Операции с кучей
Операции минимума/максимума
(C++11)
(C++17)
Операции лексикографического сравнения
Операции перестановок


Политики выполнения (C++17)
(только для демонстрации*)(C++26)

Численные операции
(C++11)
(C++17)
(C++17)    

Специализированные <memory> алгоритмы

Специализированные <random> алгоритмы
Библиотека C









 
Ограниченные алгоритмы
Все имена в этом меню принадлежат пространству имён std::ranges
Немодифицирующие операции последовательности
Модифицирующие операции последовательности
Операции разделения
Операции сортировки
Операции двоичного поиска (на отсортированных диапазонах)
       
       
Операции над множествами (на отсортированных диапазонах)
Операции с кучей
Операции минимума/максимума
       
       
Операции перестановок
Операции свёртки
Операции с неинициализированной памятью
Типы возврата
 
Определён в заголовке <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 push_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>
    push_heap( R&& r, Comp comp = {}, Proj proj = {} );
(2) (начиная с C++20)

Вставляет последний элемент указанного диапазона в кучу по отношению к comp и proj, где куча состоит из всех элементов диапазона, кроме последнего. После вставки кучей станет весь диапазон.

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

Если указанный диапазон (за исключением последнего элемента) не является кучей по отношению к comp и proj, поведение не определено.

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

Параметры

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

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

1) last

Сложность

Максимум log(N) применений comp и 2log(N) применений proj , где N это:

1) ranges:: distance ( first, last )

Возможная реализация

struct push_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
    {
        const auto n{ranges::distance(first, last)};
        const auto length{n};
        if (n > 1)
        {
            I last{first + n};
            n = (n - 2) / 2;
            I i{first + n};
            if (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *--last)))
            {
                std::iter_value_t<I> v {ranges::iter_move(last)};
                do
                {
                    *last = ranges::iter_move(i);
                    last = i;
                    if (n == 0)
                        break;
                    n = (n - 1) / 2;
                    i = first + n;
                }
                while (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, v)));
                *last = std::move(v);
            }
        }
        return first + length;
    }
    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 push_heap_fn push_heap{};

Пример

#include <algorithm>
#include <cmath>
#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<int> v{1, 6, 1, 8, 0, 3,};
    print("source vector v: ", v);
    std::ranges::make_heap(v);
    print("after make_heap: ", v);
    draw_heap(v);
    v.push_back(9);
    print("before push_heap: ", v);
    draw_heap(v);
    std::ranges::push_heap(v);
    print("after push_heap: ", v);
    draw_heap(v);
}

Вывод:

source vector v: 1 6 1 8 0 3
after make_heap: 8 6 3 1 0 1
   8
 ┌─┴─┐
 6   3
┌┴┐ ┌┴┐
1 0 1
before push_heap: 8 6 3 1 0 1 9
   8
 ┌─┴─┐
 6   3
┌┴┐ ┌┴┐
1 0 1 9
after push_heap: 9 6 8 1 0 1 3
   9
 ┌─┴─┐
 6   8
┌┴┐ ┌┴┐
1 0 1 3

См. также

проверяет, является ли диапазон максимальной кучей
(функциональный объект алгоритма)
находит наибольший поддиапазон, являющийся максимальной кучей
(функциональный объект алгоритма)
создает максимальную кучу из диапазона элементов
(функциональный объект алгоритма)
удаляет наибольший элемент из максимальной кучи
(функциональный объект алгоритма)
преобразует максимальную кучу в отсортированный диапазон элементов
(функциональный объект алгоритма)
добавляет элемент в максимальную кучу
(шаблон функции)