Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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 std

std::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.

Fuentes