Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::is_heap — verificare la proprietà di heap

std::is_heap verifica se un intervallo soddisfa la proprietà di heap senza modificarne gli elementi. Per impostazione predefinita riconosce un max-heap; un comparatore personalizzato permette di verificare un altro ordinamento, come quello di un min-heap.

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

Sintassi

#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)

std::is_heap, dichiarata in <algorithm>, restituisce bool dopo aver verificato l'intervallo [first, last). Richiede un intervallo valido e iteratori ad accesso casuale, come quelli di std::array o std::vector. Non costruisce né ripara un heap e non riordina gli elementi. Un intervallo vuoto o con un solo elemento soddisfa la condizione.

Per ogni indice del figlio i > 0, l'indice del genitore è (i - 1) / 2, usando la divisione intera. La condizione di heap richiede che comp(parent, child) sia false. Il confronto predefinito std::less{} produce un max-heap per i numeri: un genitore non è minore del figlio. std::greater<int>{} verifica un min-heap. Il comparatore deve definire un ordinamento debole stretto; usa lo stesso ordinamento impiegato per costruire l'heap.

Un heap non deve essere ordinato: non è richiesto un ordine relativo tra fratelli. La verifica ha complessità lineare rispetto al numero di elementi. Il risultato equivale a verificare std::is_heap_until(first, last, comp) == last; quest'altra funzione aiuta a individuare la prima violazione. Usa std::make_heap per costruire un heap.

L'esempio riconosce prima un max-heap, poi lo rifiuta come min-heap e infine rileva una violazione rispetto al genitore di valore 5 dopo l'assegnazione values[3] = 10. Gli overload mostrati senza una policy di esecuzione sono constexpr; esistono anche overload con policy di esecuzione. Questa voce riguarda C++23. La fonte è una bozza di standard in evoluzione e l'opzione del compilatore nel repository non certifica l'ambiente di produzione.

Esempi

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

int main() {
    std::array<int, 5> values{9, 5, 8, 1, 3};
    std::cout << std::boolalpha;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
    std::cout << std::is_heap(values.begin(), values.end(),
                              std::greater<int>{}) << '\n';
    values[3] = 10;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}

Risultato

true
false
false

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