std::ranges::sort_heap

Определён в заголовочном файле <algorithm>

Сигнатура вызова

Определён в заголовочном файле `<algorithm>`
Сигнатура вызова
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr I sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(начиная с C++20)
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> sort_heap( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(начиная с C++20)

template< std::random_access_iterator I, std::sentinel_for<I> S,
          class Comp = ranges::less, class Proj = std::identity >
    requires std::sortable<I, Comp, Proj>
constexpr I sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );

(1)

(начиная с C++20)

template< ranges::random_access_range R,
          class Comp = ranges::less, class Proj = std::identity >
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
    sort_heap( R&& r, Comp comp = {}, Proj proj = {} );

(2)

(начиная с C++20)

Сортирует элементы в указанном диапазоне относительно comp и proj, где исходно диапазон представляет собой кучу относительно comp и proj. Отсортированный диапазон больше не удовлетворяет свойству кучи.

1) Указанный диапазон — [first, last).

2) Указанный диапазон — r.

Если указанный диапазон не является кучей относительно comp и proj, поведение не определено.

Описанные на этой странице функциональные сущности — это объекты-функции алгоритмов (неофициально называемые niebloids), то есть:

При вызове любой из них нельзя указать явный список аргументов шаблона.
Ни одна из них не видна при поиске, зависимом от аргументов.
Если какая-либо из них найдена с помощью обычного неквалифицированного поиска как имя слева от оператора вызова функции, поиск, зависимый от аргументов, подавляется.

Параметры

first, last	-	пара итератора и sentinel, задающая диапазон элементов для изменения
r	-	`range` элементов для изменения
comp	-	компаратор, применяемый к спроецированным элементам
proj	-	проекция, применяемая к элементам

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

1) last

2) ranges::end(r)

Сложность

Не более \(\scriptsize 2N \cdot \log(N)\)2N⋅log(N) применений comp и \(\scriptsize 4N \cdot \log(N)\)4N⋅log(N) применений proj, где \(\scriptsize N \)N — это:

1) ranges::distance(first, last)

2) ranges::distance(r)

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

struct sort_heap_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
        requires std::sortable<I, Comp, Proj>
    constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        auto ret{ranges::next(first, last)};
        for (auto last{ret}; first != last; --last)
            ranges::pop_heap(first, last, comp, proj);
        return ret;
    }

    template<ranges::random_access_range R,
             class Comp = ranges::less, class Proj = std::identity>
        requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    }
};

inline constexpr sort_heap_fn sort_heap{};

Пример

#include <algorithm>
#include <array>
#include <iostream>

void print(auto const& rem, const auto& v)
{
    std::cout << rem;
    for (const auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}

int main()
{
    std::array v{3, 1, 4, 1, 5, 9};
    print("original array:  ", v);
    
    std::ranges::make_heap(v);
    print("after make_heap: ", v);
    
    std::ranges::sort_heap(v);
    print("after sort_heap: ", v);
}

Вывод:

original array:  3 1 4 1 5 9
after make_heap: 9 5 4 1 1 3
after sort_heap: 1 1 3 4 5 9

См. также

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

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