CKTIS / C++
std::push_heap — añadir un elemento a un montículo
std::push_heap restablece la propiedad de montículo después de añadir un elemento al final de un rango. No aumenta el tamaño del contenedor: el nuevo elemento debe estar ya en last - 1 y la parte anterior del rango debe ser un montículo válido.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap, declarado en <algorithm>, incorpora al montículo que abarca [first, last) el elemento situado en last - 1. No añade por sí mismo ningún elemento al contenedor y devuelve void. La secuencia habitual es llamar a push_back y, después, a std::push_heap con los iteradores actualizados.
Antes de la llamada, [first, last - 1) ya debe ser un montículo según el mismo orden. El rango debe contener al menos el nuevo elemento; no llames al algoritmo con un rango vacío. Para crear un montículo a partir de datos arbitrarios, usa std::make_heap en lugar de una única llamada a std::push_heap.
La comparación predeterminada produce un montículo máximo: el elemento mayor queda al principio. La sobrecarga que recibe comp cambia el orden; std::greater<int>{} produce un montículo mínimo. El comparador debe definir un orden débil estricto y ser coherente con el orden del montículo existente. Un montículo no tiene por qué estar ordenado.
Se requieren iteradores de acceso aleatorio y elementos que admitan intercambio, construcción por movimiento y asignación por movimiento. El número de comparaciones es O(log N), donde N = last - first; el coste del push_back anterior es independiente. En el ejemplo, {9, 5, 7} ya es un montículo, así que basta una llamada después de añadir 12 para restablecer la propiedad.
Ejemplos
#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';
}
Resultado
top: 12 size: 4 is_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.