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`, если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: 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 2N \cdot \log(N)\)2N⋅log(N) сравнений с использованием operator<(до C++20)std::less{}(начиная с C++20).

2) Не более \(\scriptsize 2N \cdot \log(N)\)2N⋅log(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); }

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	Применено к	Опубликованное поведение	Корректное поведение
LWG 2444	C++98	допускалось не более \(\scriptsize N \cdot \log(N)\)N⋅log(N) сравнений	увеличено до \(\scriptsize 2N \cdot \log(N)\)2N⋅log(N)

См. также

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

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