std::sort_heap
| Definido en el encabezado <algorithm>
|
||
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr desde C++20) |
template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr desde C++20) |
Convierte el montículo [first, last) en un rango ordenado. La propiedad de montículo ya no se mantiene.
operator<(hasta C++20)std::less{}(desde C++20), y se ordenará con respecto a operator<(hasta C++20)std::less{}(desde C++20).comp, y se ordenará con respecto a comp.Si se cumple alguna de las siguientes condiciones, el comportamiento no está definido:
[first,last)no es un montículo.
|
(hasta C++11) |
|
(desde C++11) |
Parámetros
| first, last | - | el par de iteradores que define el rango del montículo binario de elementos para crear el rango ordenado |
| 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)
|
| 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 ) :
Implementación posible
| sort_heap (1) |
|---|
template<class RandomIt> void sort_heap(RandomIt first, RandomIt last) { while (first != last) std::pop_heap(first, last--); } |
| sort_heap (2) |
template<class RandomIt, class Compare> void sort_heap(RandomIt first, RandomIt last, Compare comp) { while (first != last) std::pop_heap(first, last--, comp); } |
Ejemplo
#include <algorithm> #include <iostream> #include <string_view> #include <vector> void println(std::string_view fmt, const auto& v) { for (std::cout << fmt; const auto &i : v) std::cout << i << ' '; 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); std::sort_heap(v.begin(), v.end()); println("after sort_heap, v: ", v); }
Salida:
after make_heap, v: 9 4 5 1 1 3 after sort_heap, v: 1 1 3 4 5 9
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 2444 | C++98 | se permitían como máximo N⋅log(N) comparaciones | incrementado a 2N⋅log(N) |
Véase también
(C++11) |
comprueba si el rango dado es un montículo máximo (plantilla de función & objeto 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 función de algoritmo) |
(C++20) |
|
| crea un montículo máximo a partir de un rango de elementos (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
| elimina el elemento más grande de un montículo máximo (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
| añade un elemento a un montículo máximo (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
(C++20) |
convierte un montículo máximo en un rango ordenado de elementos (objeto función de algoritmo) |