CKTIS / C++
std::pop_heap — mover la raíz del heap al final
std::pop_heap mueve la raíz de un heap no vacío al final del rango y restablece el heap en el prefijo restante. No elimina ningún elemento del contenedor. En un std::vector, pop_back() solo elimina el elemento extraído si el rango del heap llega hasta el final del vector.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
std::pop_heap(first, last);
std::pop_heap(first, last, comp);std::pop_heap, declarado en <algorithm>, opera sobre [first, last). Mueve la raíz original a last - 1 y restablece un heap en [first, last - 1). De forma predeterminada, la raíz es el elemento mayor. La sobrecarga que recibe comp usa el orden proporcionado; ambas sobrecargas devuelven void.
El rango ya debe ser un heap no vacío según ese mismo orden. Los iteradores deben admitir acceso aleatorio, y los elementos deben permitir intercambio, construcción por movimiento y asignación por movimiento. El comparador debe definir un orden débil estricto. Llamar a la función con un rango vacío o con uno que no sea un heap infringe sus precondiciones.
El algoritmo no reduce el tamaño del contenedor. Después de la llamada, lee el elemento extraído mediante *(last - 1). En un std::vector, usa back() para leerlo y pop_back() para eliminarlo solo si last es igual a end() del vector. Si el rango termina antes, esas llamadas leerían y eliminarían otro elemento. Antes de otra llamada, excluye del rango el elemento extraído anteriormente. El número de comparaciones es como máximo 2 * log2(N), donde N = last - first.
El ejemplo construye un heap mediante std::make_heap e imprime solo resultados garantizados, no la disposición interna del heap. El código mostrado se ejecutó sin cambios y su salida estándar coincidió exactamente con la salida indicada. La fuente es un borrador de trabajo en evolución, no el texto fijo de C++23.
Ejemplos
#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';
}
Resultado
extracted=7 size_before=4 size_after=3 next=4 heap=true
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.