CKTIS / C++
std::pop_heap — spostare la radice dell’heap alla fine
std::pop_heap sposta la radice di un heap non vuoto alla fine dell’intervallo e ripristina l’heap nel prefisso rimanente. Non elimina alcun elemento dal contenitore. In uno std::vector, pop_back() rimuove l’elemento estratto solo se l’intervallo dell’heap arriva fino alla fine del vettore.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::pop_heap(first, last);
std::pop_heap(first, last, comp);std::pop_heap, dichiarato in <algorithm>, opera su [first, last). Sposta la radice originale in last - 1 e ripristina un heap in [first, last - 1). Per impostazione predefinita, la radice è l’elemento più grande. L’overload che riceve comp usa l’ordinamento fornito; entrambi gli overload restituiscono void.
L’intervallo deve essere già un heap non vuoto secondo lo stesso ordinamento. Gli iteratori devono supportare l’accesso casuale e gli elementi devono poter essere scambiati, costruiti per spostamento e assegnati per spostamento. Il comparatore deve definire un ordinamento debole stretto. Chiamare la funzione su un intervallo vuoto o su un intervallo che non è un heap viola le precondizioni.
L’algoritmo non riduce la dimensione del contenitore. Dopo la chiamata, leggi l’elemento estratto con *(last - 1). In uno std::vector, usa back() per leggerlo e pop_back() per rimuoverlo solo se last coincide con end() del vettore. Se l’intervallo termina prima, queste chiamate leggerebbero e rimuoverebbero un altro elemento. Prima di una nuova chiamata, escludi dall’intervallo l’elemento estratto in precedenza. Il numero di confronti è al massimo 2 * log2(N), dove N = last - first.
L’esempio crea un heap usando std::make_heap e stampa solo risultati garantiti, non la disposizione interna dell’heap. Il codice mostrato è stato eseguito senza modifiche e il suo output standard coincideva esattamente con quello riportato. La fonte è una bozza di lavoro in evoluzione, non il testo definitivo di C++23.
Esempi
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 7, 3};
std::make_heap(values.begin(), values.end());
std::pop_heap(values.begin(), values.end());
std::cout << "extracted=" << values.back() << '\n';
std::cout << "size_before=" << values.size() << '\n';
values.pop_back();
std::cout << "size_after=" << values.size() << '\n';
std::cout << "next=" << values.front() << '\n';
std::cout << "heap=" << std::boolalpha
<< std::is_heap(values.begin(), values.end()) << '\n';
}
Risultato
extracted=7 size_before=4 size_after=3 next=4 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.