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 stdstd::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.