std::make_heap
Из ru.cppreference.net
| Определён в заголовке <algorithm>
|
||
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr начиная с C++20) |
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr начиная с C++20) |
Строит кучу в диапазоне [first, last).
1) Построенная куча выполняется относительно
operator<(до C++20)std::less{}(начиная с C++20).2) Построенная куча выполняется относительно
comp.Если выполняется любое из следующих условий, поведение не определено:
|
(до C++11) |
|
(начиная с C++11) |
Параметры
| first, last | - | пара итераторов, определяющая диапазон элементов, из которых строится бинарная куча |
| comp | - | объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true если первый аргумент меньше второго.Сигнатура функции сравнения должна быть эквивалентна следующей:
Хотя сигнатура не должна содержать |
| Требования к типам | ||
-RandomIt должен удовлетворять требованиям LegacyRandomAccessIterator.
| ||
-Compare должен удовлетворять требованиям Compare.
| ||
Сложность
Пусть N равно std::distance(first, last):
1) Не более 3N сравнений с использованием
operator<(до C++20)std::less{}(начиная с C++20).2) Не более 3N применений функции сравнения
comp.Пример
Запустить этот код
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, const std::vector<int>& v = {})
{
std::cout << text << ": ";
for (const auto& e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
print("Max heap");
std::vector<int> v{3, 2, 4, 1, 5, 9};
print("initially, v", v);
std::make_heap(v.begin(), v.end());
print("after make_heap, v", v);
std::pop_heap(v.begin(), v.end());
print("after pop_heap, v", v);
auto top = v.back();
v.pop_back();
print("former top element", {top});
print("after removing the former top element, v", v);
print("\nMin heap");
std::vector<int> v1{3, 2, 4, 1, 5, 9};
print("initially, v1", v1);
std::make_heap(v1.begin(), v1.end(), std::greater<>{});
print("after make_heap, v1", v1);
std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
print("after pop_heap, v1", v1);
auto top1 = v1.back();
v1.pop_back();
print("former top element", {top1});
print("after removing the former top element, v1", v1);
}
Вывод:
Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2
Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5
Отчёты об ошибках
Следующие отчёты об ошибках, изменяющие поведение, были применены ретроспективно к ранее опубликованным стандартам C++.
| DR | Применён к | Поведение (как опубликовано) | Правильное поведение |
|---|---|---|---|
| LWG 3032 | C++98 | элементы [first, last) не требовались быть обмениваемыми
|
требуются |
См. также
(C++11) |
проверяет, является ли данный диапазон максимальной кучей (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
(C++11) |
находит наибольший поддиапазон, являющийся максимальной кучей (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
| добавляет элемент в максимальную кучу (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| удаляет наибольший элемент из максимальной кучи (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| преобразует максимальную кучу в диапазон элементов, отсортированных по возрастанию (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| адаптирует контейнер для предоставления очереди с приоритетом (шаблон класса) | |
(C++20) |
создаёт максимальную кучу из диапазона элементов (объект-функция алгоритма) |