CKTIS / C++
std::sort_heap — сортиране на съществуваща двоична купчина
std::sort_heap преобразува купчина в сортиран диапазон. Функцията изисква итератори с произволен достъп и диапазон, който е валидна купчина според сравнението, което тя използва; не е предназначена за директно сортиране на произволни данни.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
template<class RandomAccessIterator>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);std::sort_heap, декларирана в <algorithm>, сортира на място елементите от [first, last) и връща void. Диапазонът вече трябва да е валидна купчина според сравнението, което std::sort_heap използва. При произволни данни първо извикай std::make_heap или използвай директно std::sort.
Претоварването без comp подрежда числата в ненамаляващ ред. Потребителският comp трябва да дефинира строго слабо подреждане. То не е задължително да съвпада с подреждането, използвано при изграждането на купчината, стига диапазонът да е валидна купчина според comp. Например употребата на std::greater<int>{} както в std::make_heap, така и в std::sort_heap дава ненарастващ резултат. Подаването на диапазон, който не е подходяща купчина, нарушава предусловие.
Изискват се итератори с произволен достъп, а елементите трябва да отговарят на изискванията за разменяемост, конструиране чрез преместване и присвояване чрез преместване. За N = last - first алгоритъмът извършва най-много 2 N log N сравнения. Стабилността — запазването на реда на елементите, еквивалентни според сравнението — не е гарантирана. Резултатът е сортиран; не приемай, че според същия ред той все още е купчина.
Примерът първо изгражда купчина от пет числа, след което я сортира до 1 2 3 4 5. Тази статия описва класическите претоварвания на std::sort_heap, а не отделния интерфейс std::ranges::sort_heap. Източникът е текущият проект на стандарта; примерът е предназначен за локална проверка с -std=c++23.
Примери
#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>
int main() {
std::array<int, 5> values{4, 1, 5, 2, 3};
std::make_heap(values.begin(), values.end());
std::sort_heap(values.begin(), values.end());
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
}
Резултат
1 2 3 4 5
Показаният код и посоченият резултат са проверени в изолирана среда по метода, описан в записа за проверката на точно тази версия.