CKTIS / C++
std::make_heap — crear un heap a partir de un rango
std::make_heap reorganiza un rango para convertirlo en un heap en tiempo lineal. De forma predeterminada, el elemento mayor queda al principio; un comparador personalizado permite crear un heap mínimo. No se garantiza que el rango resultante esté ordenado.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
namespace std {
template<class RandomAccessIterator>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
} // namespace stdstd::make_heap, declarado en <algorithm>, transforma [first, last) en un heap, reorganiza sus elementos y devuelve void. No es necesario que el rango ya sea un heap. La comparación predeterminada crea un heap máximo: para un rango no vacío, *first es el elemento mayor. Esto no ordena todo el rango; la disposición exacta de los demás elementos no está especificada.
La sobrecarga que recibe comp crea un heap según ese comparador. Para cada hijo, comp(parent, child) debe ser falso. std::greater<int>{} de <functional> produce un heap mínimo. El comparador debe definir un orden débil estricto; no uses <= en lugar de <.
Se requieren iteradores de acceso aleatorio, y los elementos deben admitir intercambio, construcción por movimiento y asignación por movimiento. Para N = last - first, el algoritmo realiza como máximo 3 * N comparaciones, por lo que la complejidad en comparaciones es lineal. Un rango vacío es válido, pero en ese caso no debes leer *first ni front().
El ejemplo comprueba la raíz y la propiedad de heap, en lugar de presuponer una disposición concreta de todos los elementos. Mantén el mismo orden en las operaciones posteriores: std::push_heap, std::pop_heap y std::sort_heap deben usar un comparador compatible. std::pop_heap por sí sola no elimina ningún elemento del contenedor.
Ejemplos
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 7, 3, 2};
std::make_heap(values.begin(), values.end());
std::cout << "max: " << values.front() << '\n';
std::cout << std::boolalpha
<< "heap: " << std::is_heap(values.begin(), values.end()) << '\n';
std::make_heap(values.begin(), values.end(), std::greater<int>{});
std::cout << "min: " << values.front() << '\n';
}Resultado
max: 7 heap: true min: 1
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.