CKTIS / C++
std::sort_heap — sortowanie gotowego kopca
std::sort_heap przekształca kopiec w posortowany zakres. Wymaga iteratorów dostępu swobodnego i zakresu będącego poprawnym kopcem według porównania stosowanego przez funkcję; nie służy do bezpośredniego sortowania dowolnych danych.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#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 z nagłówka <algorithm> sortuje elementy zakresu [first, last) w miejscu i zwraca void. Zakres musi już być poprawnym kopcem według porównania stosowanego przez std::sort_heap. Dla dowolnych danych najpierw wywołaj std::make_heap albo użyj bezpośrednio std::sort.
Przeciążenie bez comp daje porządek niemalejący dla liczb. Własny comp musi definiować ścisły słaby porządek. Porządek ten nie musi być taki sam jak porządek użyty przy budowaniu kopca, o ile zakres jest poprawnym kopcem według comp. Na przykład std::greater<int>{} użyte zarówno w std::make_heap, jak i std::sort_heap daje wynik nierosnący. Przekazanie zakresu, który nie jest odpowiednim kopcem, narusza warunek wstępny.
Wymagane są iteratory dostępu swobodnego oraz elementy spełniające wymagania zamiany, konstrukcji przez przeniesienie i przypisania przez przeniesienie. Dla N = last - first algorytm wykonuje najwyżej 2 N log N porównań. Nie gwarantuje stabilności, czyli zachowania kolejności elementów równoważnych według porównania. Wynik jest posortowany; nie należy zakładać, że nadal jest kopcem według tego samego porządku.
Przykład najpierw buduje kopiec z pięciu liczb, a następnie sortuje go do 1 2 3 4 5. Opis dotyczy klasycznych przeciążeń std::sort_heap, a nie osobnego interfejsu std::ranges::sort_heap. Źródłem jest bieżący szkic standardu; przykład przeznaczono do lokalnej weryfikacji z flagą -std=c++23.
Przykłady
#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';
}
Wynik
1 2 3 4 5
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.