std::push_heap

Определено в заголовке `<algorithm>`
	(1)
template< class RandomIt > void push_heap( RandomIt first, RandomIt last );		(до C++20)
template< class RandomIt > constexpr void push_heap( RandomIt first, RandomIt last );		(с C++20)
	(2)
template< class RandomIt, class Compare > void push_heap( RandomIt first, RandomIt last, Compare comp );		(до C++20)
template< class RandomIt, class Compare > constexpr void push_heap( RandomIt first, RandomIt last, Compare comp );		(с C++20)

Вставляет элемент в позицию last - 1 в кучу [first, last - 1). Куча после вставки будет [first, last).

1) Куча с точки зрения operator<.

2) Куча с точки зрения comp.

Если [first, last - 1) не является кучей, поведение не определено.

Параметры

first, last	-	диапазон, указывающий кучу после вставки
comp	-	объект-функция сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго. Подпись функции сравнения должна быть эквивалентна следующей: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не обязана иметь `const&`, функция не должна изменять объекты, переданные ей, и должна быть способна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` недопустимо, а также `Type1` за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать, а затем неявно преобразовать в оба из них.
Требования к типу
-`RandomIt` должно соответствовать требованиям LegacyRandomAccessIterator.
-Тип разыменованного `RandomIt` должен соответствовать требованиям MoveAssignable и MoveConstructible.
-`Compare` должно соответствовать требованиям Compare.

Значение результата

(нет)

Сложность

Дано \(\scriptsize N\)N как std::distance(first, last):

1) Не более \(\scriptsize log(N)\)log(N) сравнений с использованием operator<.

2) Не более \(\scriptsize log(N)\)log(N) применений функции сравнения comp.

Примечания

Куча с точки зрения comp (максимальная куча) — это диапазон случайного доступа [first, last) с следующими свойствами:

Дано \(\scriptsize N\)N как last - first, для всех целых i где \(\scriptsize 0 < i < N\)0 < i < N, bool(comp(first[(i - 1) / 2], first[i])) является false.
Новый элемент можно добавить, используя std::push_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).
*first можно удалить, используя std::pop_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).

Пример

#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
 
void println(std::string_view rem, std::vector<int> const& v)
{
    std::cout << rem;
    for (int e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
 
    std::make_heap(v.begin(), v.end());
    println("after make_heap: ", v);
 
    v.push_back(6);
    println("after push_back: ", v);
 
    std::push_heap(v.begin(), v.end());
    println("after push_heap: ", v);
}

Вывод:

after make_heap: 9 5 4 1 1 3
after push_back: 9 5 4 1 1 3 6
after push_heap: 9 5 6 1 1 3 4

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применено к	Поведение, как опубликовано	Корректное поведение
LWG 193	C++98	куча требовала `*first` быть максимальным элементом	могут быть элементы, равные `*first`
LWG 2166	C++98	требование кучи не достаточно точно соответствовало определению максимальной кучи	улучшенное требование

См. также

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

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