Namespaces
Variants

std:: make_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 make_heap ( RandomIt first, RandomIt last ) ;
(1) (constexpr desde C++20)
template < class RandomIt, class Compare >
void make_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(2) (constexpr desde C++20)

Construye un heap en el rango [ first , last ) .

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

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

(hasta C++11)
(desde C++11)

Contenidos

Parámetros

first, last - el par de iteradores que define el rango de elementos para hacer el rango de montículo binario
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 3N comparaciones usando operator < (until C++20) std:: less { } (since C++20) .
2) Como máximo 3N aplicaciones de la función de comparación comp .

Ejemplo

Ejecutar este código 
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, const std::vector<int>& v = {})
{
    std::cout << text << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    print("Max heap");
    std::vector<int> v{3, 2, 4, 1, 5, 9};
    print("initially, v", v);
    std::make_heap(v.begin(), v.end());
    print("after make_heap, v", v);
    std::pop_heap(v.begin(), v.end());
    print("after pop_heap, v", v);
    auto top = v.back();
    v.pop_back();
    print("former top element", {top});
    print("after removing the former top element, v", v);
    print("\nMin heap");
    std::vector<int> v1{3, 2, 4, 1, 5, 9};
    print("initially, v1", v1);
    std::make_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after make_heap, v1", v1);
    std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after pop_heap, v1", v1);
    auto top1 = v1.back();
    v1.pop_back();
    print("former top element", {top1});
    print("after removing the former top element, v1", v1);
}

Salida: 

Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2
Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5

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)
agrega un elemento a un montículo máximo
(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)
adapta un contenedor para proporcionar una cola de prioridad
(plantilla de clase)
(C++20)
crea un montículo máximo a partir de un rango de elementos
(objeto función de algoritmo)