Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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.

Źródła