CKTIS / C++
std::is_heap — verificar a propriedade de heap
std::is_heap verifica se um intervalo satisfaz a propriedade de heap sem alterar os seus elementos. Por predefinição, reconhece um max-heap; um comparador personalizado permite verificar outra ordenação, como a de um min-heap.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)std::is_heap, declarada em <algorithm>, devolve bool depois de verificar o intervalo [first, last). Requer um intervalo válido e iteradores de acesso aleatório, como os de std::array ou std::vector. Não constrói nem repara um heap e não reordena os elementos. Um intervalo vazio ou com um único elemento satisfaz a condição.
Para cada índice de filho i > 0, o índice do pai é (i - 1) / 2, usando divisão inteira. A condição de heap exige que comp(parent, child) seja false. A comparação predefinida std::less{} produz um max-heap para números: um pai não é menor do que o filho. std::greater<int>{} verifica um min-heap. O comparador tem de definir uma ordem fraca estrita; use a mesma ordenação que foi usada para construir o heap.
Um heap não tem de estar ordenado: não é exigida qualquer ordenação relativa entre irmãos. A verificação tem complexidade linear em relação ao número de elementos. O resultado equivale a testar std::is_heap_until(first, last, comp) == last; essa outra função ajuda a localizar a primeira violação. Use std::make_heap para construir um heap.
O exemplo reconhece primeiro um max-heap, depois rejeita-o como min-heap e, por fim, deteta uma violação em relação ao pai de valor 5 após a atribuição values[3] = 10. As sobrecargas apresentadas sem política de execução são constexpr; também existem sobrecargas com política de execução. Esta entrada diz respeito a C++23. A fonte é um projeto de norma em evolução, e a opção do compilador no repositório não atesta o ambiente de produção.
Exemplos
#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
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.