Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::sort_heap — ordinare un heap esistente

std::sort_heap trasforma un heap in un intervallo ordinato. Richiede iteratori ad accesso casuale e un intervallo che sia un heap valido secondo il confronto usato dalla funzione; non ordina direttamente dati arbitrari.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

#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, dichiarato in <algorithm>, ordina sul posto gli elementi di [first, last) e restituisce void. L’intervallo deve essere già un heap valido secondo il confronto usato da std::sort_heap. Per dati arbitrari, chiama prima std::make_heap oppure usa direttamente std::sort.

L’overload senza comp produce un ordine non decrescente per i numeri. Un comp personalizzato deve definire un ordinamento debole stretto. L’ordinamento non deve necessariamente coincidere con quello usato per costruire l’heap, purché l’intervallo sia un heap valido secondo comp. Per esempio, usare std::greater<int>{} sia in std::make_heap sia in std::sort_heap produce un risultato non crescente. Passare un intervallo che non è un heap appropriato viola una precondizione.

Sono richiesti iteratori ad accesso casuale e gli elementi devono soddisfare i requisiti di scambiabilità, costruzione per spostamento e assegnazione per spostamento. Per N = last - first, l’algoritmo esegue al massimo 2 N log N confronti. La stabilità — cioè il mantenimento dell’ordine degli elementi equivalenti secondo il confronto — non è garantita. Il risultato è ordinato; non presumere che resti un heap secondo lo stesso ordinamento.

L’esempio crea prima un heap con cinque numeri, poi lo ordina ottenendo 1 2 3 4 5. Questa voce descrive gli overload classici di std::sort_heap, non l’interfaccia separata std::ranges::sort_heap. La fonte è la bozza attuale dello standard; l’esempio è destinato alla verifica locale con -std=c++23.

Esempi

#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';
}

Risultato

1 2 3 4 5

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti