std::make_heap

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

Создаёт кучу в диапазоне [first, last).

1) Созданная куча соответствует operator<.

2) Созданная куча соответствует comp.

Параметры

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 3N\)3N сравнений, использующих operator<.

2) Не более \(\scriptsize 3N\)3N применений функции сравнения 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 <functional>
#include <iostream>
#include <string_view>
#include <vector>
 
void print(std::string_view text, std::vector<int> const& 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 193	C++98	куча требовала `*first` быть наибольшим элементом	могут быть элементы, равные `*first`
LWG 2166	C++98	требование кучи не соответствовало достаточно точно определению максимальной кучи	требование улучшено

См. также

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

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