Namespaces
Variants

std:: push_heap

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Definido en el encabezado <algorithm>
template < class RandomIt >
void push_heap ( RandomIt first, RandomIt last ) ;
(1) (constexpr desde C++20)
template < class RandomIt, class Compare >
void push_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(2) (constexpr desde C++20)

Inserta el elemento en la posición last - 1 en el heap [ first , last - 1 ) . El heap después de la inserción será [ first , last ) .

1) El heap es con respecto a operator < (until C++20) std:: less { } (since C++20) .
2) El montículo es con respecto a comp .

Si se satisface cualquiera de las siguientes condiciones, el comportamiento es indefinido:

  • [ first , last - 1 ) no es un heap con respecto al comparador correspondiente.
(hasta C++11)
(desde C++11)

Contenidos

Parámetros

first, last - el par de iteradores que definen el rango de elementos que forman el montículo binario después de la inserción
comp - objeto función de comparación (es decir, un objeto que satisface los requisitos de Compare ) que devuelve true si el primer argumento es menor que el segundo.

La firma de la función de comparación debe ser equivalente a la siguiente:

bool cmp ( const Type1 & a, const Type2 & b ) ;

Aunque la firma no necesita tener const & , la función no debe modificar los objetos pasados a ella y debe poder aceptar todos los valores de tipo (posiblemente const) Type1 y Type2 independientemente de la categoría de valor (por lo tanto, Type1 & no está permitido , ni tampoco Type1 a menos que para Type1 un movimiento sea equivalente a una copia (desde C++11) ).
Los tipos Type1 y Type2 deben ser tales que un objeto de tipo RandomIt pueda ser desreferenciado y luego convertido implícitamente a ambos.

Requisitos de tipo
-
RandomIt debe cumplir con los requisitos de LegacyRandomAccessIterator .
-
Compare debe cumplir con los requisitos de Compare .

Complejidad

Dado N como std:: distance ( first, last ) :

1) Como máximo log(N) comparaciones usando operator < (hasta C++20) std:: less { } (desde C++20) .
2) Como máximo log(N) aplicaciones de la función de comparación comp .

Ejemplo

Ejecutar este código 
#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view rem, const std::vector<int>& v)
{
    std::cout << rem;
    for (int e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
    std::make_heap(v.begin(), v.end());
    println("after make_heap: ", v);
    v.push_back(6);
    println("after push_back: ", v);
    std::push_heap(v.begin(), v.end());
    println("after push_heap: ", v);
}

Salida: 

after make_heap: 9 5 4 1 1 3
after push_back: 9 5 4 1 1 3 6
after push_heap: 9 5 6 1 1 3 4

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

DR Aplicado a Comportamiento publicado Comportamiento correcto
LWG 3032 C++98 los elementos de [ first , last ) no se requería que fueran intercambiables requerido

Véase también

(C++11)
verifica si el rango dado es un montículo máximo
(plantilla de función)
(C++11)
encuentra el mayor subrango que es un montículo máximo
(plantilla de función)
crea un montículo máximo a partir de un rango de elementos
(plantilla de función)
elimina el elemento más grande de un montículo máximo
(plantilla de función)
convierte un montículo máximo en un rango de elementos ordenados en orden ascendente
(plantilla de función)
(C++20)
agrega un elemento a un montículo máximo
(objeto función de algoritmo)