Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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.

Fuentes