std::push_heap
| Определено в заголовке <algorithm>
|
||
template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr начиная с C++20) |
template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr начиная с C++20) |
Вставляет элемент в позицию last - 1 в кучу [first, last - 1). После вставки куча будет [first, last).
operator<(до C++20)std::less{}(начиная с C++20).comp.Если выполняется любое из следующих условий, поведение не определено:
[first,last - 1)не является кучей относительно соответствующего компаратора.
|
(до C++11) |
|
(начиная с C++11) |
Параметры
| first, last | - | пара итераторов, определяющих диапазон элементов, образующих бинарную кучу после вставки |
| comp | - | функциональный объект сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true если первый аргумент меньше второго.Сигнатура функции сравнения должна быть эквивалентна следующей:
Хотя сигнатура не должна содержать |
| Требования к типам | ||
-RandomIt должен удовлетворять требованиям LegacyRandomAccessIterator.
| ||
-Compare должен удовлетворять требованиям Compare.
| ||
Сложность
Пусть N равно std::distance(first, last):
operator<(до C++20)std::less{}(начиная с C++20).comp.Пример
#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view rem, const std::vector<int>& 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 3032 | C++98 | элементы [first, last) не требовались быть обмениваемыми
|
требуются |
См. также
(C++11) |
проверяет, является ли заданный диапазон максимальной кучей (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
(C++11) |
находит наибольший поддиапазон, являющийся максимальной кучей (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
| создаёт максимальную кучу из диапазона элементов (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| удаляет наибольший элемент из максимальной кучи (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| превращает максимальную кучу в диапазон элементов, отсортированных по возрастанию (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
(C++20) |
добавляет элемент в максимальную кучу (объект-функция алгоритма) |