Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::make_heap — creare un heap da un intervallo

std::make_heap riordina un intervallo trasformandolo in un heap in tempo lineare. Per impostazione predefinita, l’elemento più grande si trova all’inizio; un comparatore personalizzato consente di creare un min-heap. Non è garantito che l’intervallo risultante sia ordinato.

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

Sintassi

#include <algorithm>

namespace std {

template<class RandomAccessIterator>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

} // namespace std

std::make_heap, dichiarato in <algorithm>, trasforma [first, last) in un heap, riordinandone gli elementi e restituendo void. L’intervallo non deve essere già un heap. Il confronto predefinito crea un max-heap: per un intervallo non vuoto, *first è l’elemento più grande. Questo non ordina l’intero intervallo; la disposizione esatta degli altri elementi non è specificata.

L’overload che accetta comp crea un heap secondo quel comparatore. Per ogni figlio, comp(parent, child) deve essere falso. std::greater<int>{} da <functional> produce un min-heap. Il comparatore deve definire un ordinamento debole stretto; non usare <= al posto di <.

Sono necessari iteratori ad accesso casuale e gli elementi devono supportare lo scambio, la costruzione per spostamento e l’assegnazione per spostamento. Per N = last - first, l’algoritmo esegue al massimo 3 * N confronti, quindi la complessità in termini di confronti è lineare. Un intervallo vuoto è valido, ma in tal caso non bisogna leggere né *first né front().

L’esempio controlla la radice e la proprietà di heap, senza presupporre una disposizione particolare di tutti gli elementi. Mantieni lo stesso ordinamento nelle operazioni successive: std::push_heap, std::pop_heap e std::sort_heap devono usare un comparatore compatibile. std::pop_heap da solo non rimuove un elemento dal contenitore.

Esempi

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 7, 3, 2};

    std::make_heap(values.begin(), values.end());
    std::cout << "max: " << values.front() << '\n';
    std::cout << std::boolalpha
              << "heap: " << std::is_heap(values.begin(), values.end()) << '\n';

    std::make_heap(values.begin(), values.end(), std::greater<int>{});
    std::cout << "min: " << values.front() << '\n';
}

Risultato

max: 7
heap: true
min: 1

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