CKTIS / C++
std::sort_heap — ordenar un heap existente
std::sort_heap convierte un heap en un rango ordenado. Requiere iteradores de acceso aleatorio y un rango que sea un heap válido según la comparación que usa la función; no sirve para ordenar directamente datos arbitrarios.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
template<class RandomAccessIterator>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);std::sort_heap, declarado en <algorithm>, ordena in situ los elementos de [first, last) y devuelve void. El rango ya debe ser un heap válido según la comparación que usa std::sort_heap. Para datos arbitrarios, llama primero a std::make_heap o usa directamente std::sort.
La sobrecarga sin comp produce un orden no decreciente para números. Un comp personalizado debe definir un orden débil estricto. Ese orden no tiene por qué coincidir con el que se usó para construir el heap, siempre que el rango sea un heap válido según comp. Por ejemplo, usar std::greater<int>{} tanto en std::make_heap como en std::sort_heap produce un resultado no creciente. Pasar un rango que no sea un heap adecuado incumple una precondición.
Se requieren iteradores de acceso aleatorio, y los elementos deben cumplir los requisitos de intercambiabilidad, construcción por movimiento y asignación por movimiento. Para N = last - first, el algoritmo realiza como máximo 2 N log N comparaciones. No se garantiza la estabilidad, es decir, que se conserve el orden de los elementos equivalentes según la comparación. El resultado queda ordenado; no des por hecho que sigue siendo un heap según el mismo orden.
El ejemplo primero construye un heap con cinco números y luego lo ordena para obtener 1 2 3 4 5. Esta entrada describe las sobrecargas clásicas de std::sort_heap, no la interfaz independiente std::ranges::sort_heap. La fuente es el borrador actual del estándar; el ejemplo está pensado para verificarse localmente con -std=c++23.
Ejemplos
#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>
int main() {
std::array<int, 5> values{4, 1, 5, 2, 3};
std::make_heap(values.begin(), values.end());
std::sort_heap(values.begin(), values.end());
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
}
Resultado
1 2 3 4 5
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.