std::make_heap
| 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 montículo en el rango [first, last).
operator<(hasta C++20)std::less{}(desde C++20).comp.Si se cumple alguna de las siguientes condiciones, el comportamiento no está definido:
|
(hasta C++11) |
|
(desde C++11) |
Parámetros
| first, last | - | el par de iteradores que definen el rango de elementos para convertir en el rango del 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:
Aunque la firma no necesita tener |
| Requisitos de tipo | ||
-RandomIt debe cumplir los requisitos de LegacyRandomAccessIterator.
| ||
-Compare debe cumplir los requisitos de Compare.
| ||
Complejidad
Dado N como std::distance(first, last):
operator<(hasta C++20)std::less{}(desde C++20).comp.Ejemplo
#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 cambian el comportamiento se aplicaron retroactivamente a los estándares C++ publicados anteriormente.
| DR | Aplicado a | Comportamiento publicado | Comportamiento correcto |
|---|---|---|---|
| LWG 3032 | C++98 | no se requería que los elementos de [first, last) fueran intercambiables
|
requerido |
Véase también
(C++11) |
comprueba si el rango dado es un montículo máximo (plantilla de función & objeto de función de algoritmo) |
(C++20) |
|
(C++11) |
encuentra el subrango más grande que es un montículo máximo (plantilla de función & objeto de función de algoritmo) |
(C++20) |
|
| añade un elemento a un montículo máximo (plantilla de función & objeto de función de algoritmo) | |
(C++20) |
|
| elimina el elemento más grande de un montículo máximo (plantilla de función & objeto de función de algoritmo) | |
(C++20) |
|
| convierte un montículo máximo en un rango de elementos ordenados en orden ascendente (plantilla de función & objeto de función de algoritmo) | |
(C++20) |
|
| 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 de función de algoritmo) |