std::sort_heap

Определён в заголовочном файле `<algorithm>`
template< class RandomIt > void sort_heap( RandomIt first, RandomIt last );	(1)	(constexpr начиная с C++20)
template< class RandomIt, class Compare > void sort_heap( RandomIt first, RandomIt last, Compare comp );	(2)	(constexpr начиная с C++20)

Преобразует кучу [first, last) в отсортированный диапазон. Свойство кучи больше не поддерживается.

1) Куча строится относительно operator<(до C++20)std::less{}(начиная с C++20), и будет отсортирована относительно operator<(до C++20)std::less{}(начиная с C++20).

2) Куча строится относительно comp, и будет отсортирована относительно comp.

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

[first, last) не является кучей.

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

Параметры

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 .
- `Compare` должен удовлетворять требованиям Compare .

Сложность

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

1) Не более

2N\cdotlog(N)

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

2) Не более

2N\cdotlog(N)

применений функции сравнения comp .

Возможная реализация

sort_heap (1)

template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last)
{
    while (first != last)
        std::pop_heap(first, last--);
}

sort_heap (2)

template<class RandomIt, class Compare>
void sort_heap(RandomIt first, RandomIt last, Compare comp)
{
    while (first != last)
        std::pop_heap(first, last--, comp);
}

Пример

Запустить этот код

#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view fmt, const auto& v)
{
    for (std::cout << fmt; const auto &i : v)
        std::cout << i << ' ';
    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);
    std::sort_heap(v.begin(), v.end());
    println("after sort_heap, v: ", v);
}

Вывод:

after make_heap, v: 9 4 5 1 1 3
after sort_heap, v: 1 1 3 4 5 9

Отчёты о дефектах

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

DR	Applied to	Behavior as published	Correct behavior
LWG 2444	C++98	at most $N\cdotlog(N)$ comparisons were allowed	increased to $2N\cdotlog(N)$

См. также

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

Поддержка компиляторов
Автономное и хостируемое окружение
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Именованные требования
Макросы тестирования возможностей (C++20)
Библиотека поддержки языка
Библиотека концептов (C++20)
Библиотека диагностики
Библиотека управления памятью
Библиотека метапрограммирования (C++11)
Библиотека общих утилит
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека строк
Библиотека обработки текста
Библиотека численных операций
Библиотека даты и времени
Библиотека ввода-вывода
Библиотека файловой системы (C++17)
Библиотека поддержки параллелизма (C++11)
Библиотека управления выполнением (C++26)
Технические спецификации
Указатель символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants