HOWTO · C++
Usa algoritmi heap STL in C++
Questo articolo introduce come utilizzare gli algoritmi di heap STL in C++.
In questa pagina
Usa gli algoritmi heap della STL di C++ per trasformare un intervallo di std::vector in un max-heap, ordinarlo oppure spostare il valore più grande alla fine. std::pop_heap sposta il valore; per rimuoverlo dal vettore, cancellalo separatamente.
Usa la funzione std::make_heap per convertire un intervallo in un heap
Un heap è un intervallo organizzato secondo una relazione tra genitori e figli. Con il confronto predefinito, std::make_heap crea un max-heap: ogni genitore è maggiore o uguale ai propri figli, quindi il valore più grande si trova all’inizio. In un heap binario basato su un vettore, i figli dell’elemento all’indice i si trovano agli indici 2 * i + 1 e 2 * i + 2, se queste posizioni rientrano nell’intervallo. Per creare un min-heap si usa un confronto diverso, per esempio std::greater<int>.
std::make_heap riordina gli elementi in modo da soddisfare la proprietà di heap, ma non ordina completamente l’intervallo. Molte disposizioni diverse possono rispettare la stessa proprietà; perciò, dopo la chiamata, il codice dovrebbe basarsi sul valore iniziale e sui confronti tra genitori e figli, non su una particolare sequenza di valori.
L’esempio autonomo seguente crea un heap e verifica la relazione tra genitori e figli. È stato eseguito correttamente. Nell’output qui sotto, le etichette sono in inglese: indicano che il controllo del max-heap è vero e che il valore in cima è 91.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
std::make_heap(values.begin(), values.end());
bool is_max_heap = true;
for (std::size_t child = 1; child < values.size(); ++child) {
const std::size_t parent = (child - 1) / 2;
if (values[parent] < values[child]) {
is_max_heap = false;
break;
}
}
std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
std::cout << "top: " << values.front() << '\n';
}
max-heap: true
top: 91
L’elemento iniziale è il valore in cima all’heap. L’ordine degli altri elementi del vettore è vincolato solo dalla proprietà di heap: non va quindi interpretato come una lista crescente o decrescente.
Usa la funzione std::sort_heap per ordinare un intervallo heap
Chiama std::sort_heap su un intervallo che soddisfa già la proprietà di heap. Con il confronto predefinito, la funzione riordina l’intervallo in ordine crescente. Dopo l’ordinamento, l’intervallo non soddisfa più la proprietà di heap: prima di usare un algoritmo heap sull’intero intervallo, chiama di nuovo std::make_heap.
Per esempio, dopo std::make_heap(values.begin(), values.end()), chiama std::sort_heap(values.begin(), values.end()) per ordinare lo stesso intervallo. Il confronto predefinito produce un ordine crescente.
L’overload con comparatore accetta una funzione o un oggetto funzione che definisce l’ordinamento. Usa lo stesso confronto quando costruisci e ordini un heap; per esempio, un heap creato con std::greater<int> deve essere ordinato usando lo stesso comparatore. L’overload predefinito è adatto quando vuoi ottenere un risultato crescente.
Usa la funzione std::pop_heap per spostare l’elemento successivo dell’heap
std::pop_heap sposta il valore in cima all’ultima posizione dell’intervallo e ripristina la proprietà di heap nell’intervallo precedente. Non modifica la dimensione del vettore. Per rimuovere quel valore dal contenitore, dopo std::pop_heap chiama pop_back().
Per aggiungere un elemento, inseriscilo in fondo al vettore e chiama std::push_heap. L’intervallo che precede l’elemento aggiunto deve già essere un heap; std::push_heap ripristina quindi la proprietà di heap nell’intervallo ampliato. Per entrambi gli algoritmi, usa lo stesso comparatore che definisce l’heap.
Questo esempio autonomo verifica il valore in cima spostato, lo cancella separatamente e poi aggiunge un valore mantenendo l’heap. È stato eseguito correttamente. Nell’output qui sotto, le etichette sono in inglese: indicano che il valore spostato in fondo è 91 e che il nuovo valore in cima è 95.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
std::make_heap(values.begin(), values.end());
std::pop_heap(values.begin(), values.end());
std::cout << "moved top: " << values.back() << '\n';
values.pop_back();
values.push_back(95);
std::push_heap(values.begin(), values.end());
std::cout << "new top: " << values.front() << '\n';
}
moved top: 91
new top: 95
Dopo std::pop_heap, il prefisso che termina prima dell’ultimo elemento è l’heap da riutilizzare. Quando pop_back() rimuove l’ultimo valore, il vettore contiene di nuovo esattamente quell’intervallo heap. Aggiungere un elemento senza prima preservare questa proprietà non soddisfa il prerequisito di std::push_heap.
