Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes