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

CKTIS / C++

std::is_heap — comprobar la propiedad de heap

std::is_heap comprueba si un rango cumple la propiedad de heap sin modificar sus elementos. De forma predeterminada reconoce un max-heap; un comparador personalizado permite comprobar otro orden, como el de un min-heap.

Versión: C++23; repository compiler flag, production runtime not attested

Sintaxis

#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)

std::is_heap, declarada en <algorithm>, devuelve bool después de comprobar el rango [first, last). Requiere un rango válido e iteradores de acceso aleatorio, como los de std::array o std::vector. No construye ni repara un heap, y tampoco reordena los elementos. Un rango vacío o con un solo elemento cumple la condición.

Para cada índice de hijo i > 0, el índice del padre es (i - 1) / 2, usando división entera. La condición de heap exige que comp(parent, child) sea false. La comparación predeterminada std::less{} da un max-heap para números: un padre no es menor que su hijo. std::greater<int>{} comprueba un min-heap. El comparador debe definir un orden débil estricto; usa el mismo orden que se utilizó para construir el heap.

Un heap no tiene que estar ordenado: no se requiere ningún orden relativo entre hermanos. La comprobación tiene complejidad lineal respecto al número de elementos. El resultado equivale a comprobar std::is_heap_until(first, last, comp) == last; esa otra función ayuda a localizar la primera infracción. Usa std::make_heap para construir un heap.

El ejemplo reconoce primero un max-heap, luego lo rechaza como min-heap y, por último, detecta una infracción respecto al padre de valor 5 tras asignar values[3] = 10. Las sobrecargas mostradas sin política de ejecución son constexpr; también existen sobrecargas con política de ejecución. Esta entrada corresponde a C++23. La fuente es un borrador de estándar en evolución, y la opción del compilador del repositorio no acredita el entorno de producción.

Ejemplos

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
    std::array<int, 5> values{9, 5, 8, 1, 3};
    std::cout << std::boolalpha;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
    std::cout << std::is_heap(values.begin(), values.end(),
                              std::greater<int>{}) << '\n';
    values[3] = 10;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}

Resultado

true
false
false

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