CKTIS / C++
std::push_heap — aggiungere un elemento a un heap
std::push_heap ripristina la proprietà di heap dopo che un elemento è stato aggiunto alla fine di un intervallo. Non aumenta la dimensione del contenitore: il nuovo elemento deve trovarsi già in last - 1 e la parte precedente dell’intervallo deve essere un heap valido.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap, dichiarato in <algorithm>, incorpora l’elemento in last - 1 nell’heap che copre [first, last). Non aggiunge autonomamente elementi al contenitore e restituisce void. La sequenza abituale consiste nel chiamare push_back e poi std::push_heap con gli iteratori aggiornati.
Prima della chiamata, [first, last - 1) deve essere già un heap secondo lo stesso ordinamento. L’intervallo deve contenere almeno il nuovo elemento; non chiamare l’algoritmo su un intervallo vuoto. Per costruire un heap da dati arbitrari, usa std::make_heap invece di una singola chiamata a std::push_heap.
Il confronto predefinito produce un max-heap: l’elemento più grande si trova all’inizio. L’overload che accetta comp cambia l’ordinamento; std::greater<int>{} produce un min-heap. Il comparatore deve definire un ordinamento debole stretto ed essere coerente con l’ordinamento dell’heap esistente. Un heap non deve essere necessariamente ordinato.
Sono richiesti iteratori ad accesso casuale ed elementi che supportino lo scambio, la costruzione per spostamento e l’assegnazione per spostamento. Il numero di confronti è O(log N), dove N = last - first; il costo del precedente push_back è separato. Nell’esempio, {9, 5, 7} è già un heap, quindi dopo aver aggiunto 12 basta una chiamata per ripristinare la proprietà di heap.
Esempi
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> heap{9, 5, 7};
heap.push_back(12);
std::push_heap(heap.begin(), heap.end());
std::cout << "top: " << heap.front() << '\n';
std::cout << "size: " << heap.size() << '\n';
std::cout << "is_heap: " << std::boolalpha
<< std::is_heap(heap.begin(), heap.end()) << '\n';
}
Risultato
top: 12 size: 4 is_heap: true
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.