std::sort_heap

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

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

1) [first, last) является кучей относительно operator<, и будет отсортирована относительно operator<.

2) [first, last) является кучей относительно comp, и будет отсортирована относительно comp.

Если [first, last) не является кучей, поведение не определено.

Параметры

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` должен удовлетворять требованиям ValueSwappable и LegacyRandomAccessIterator.
-Тип дереференцированного `RandomIt` должен удовлетворять требованиям MoveAssignable и MoveConstructible.
-`Compare` должен удовлетворять требованиям Compare.

Возвращаемое значение

(ничего)

Сложность

Учитывая \(\scriptsize N\)N как std::distance(first, last):

1) Не более \(\scriptsize 2N \cdot log(N)\)2N·log(N) сравнений с использованием operator<.

2) Не более \(\scriptsize 2N \cdot log(N)\)2N·log(N) применений функции сравнения comp.

Примечания

Куча относительно comp (максимальная куча) — это диапазон произвольного доступа range [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) времени.

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

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); }

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, auto const& 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	Применимо к	Поведение, как опубликовано	Правильное поведение
LWG 193	C++98	heap требовал `*first` быть максимальным элементом	могут быть элементы, равные `*first`
LWG 2166	C++98	требование к куче не достаточно точно соответствовало определению максимальной кучи	улучшенное требование
LWG 2444	C++98	разрешалось не более \(\scriptsize N \cdot log(N)\)N·log(N) сравнений	увеличено до \(\scriptsize 2N \cdot log(N)\)2N·log(N)

См. также

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

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