std::make_heap

Определён в заголовочном файле `<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.

Поведение не определено, если выполняется любое из следующих условий:

Тип `*first` не удовлетворяет требованиям Swappable.	(до C++11)
`RandomIt` не удовлетворяет требованиям ValueSwappable. Тип `first` не удовлетворяет требованиям MoveConstructible. Тип `first` не удовлетворяет требованиям MoveAssignable.	(начиная с C++11)

Параметры

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

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1) Не более \(\scriptsize 3N\)3N сравнений с использованием operator<(до C++20)std::less{}(начиная с C++20).

2) Не более \(\scriptsize 3N\)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)` не требовалось, чтобы они были Swappable	требуется

См. также

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

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