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

CKTIS / C++

std::make_heap — criar um heap a partir de um intervalo

std::make_heap reorganiza um intervalo para o transformar num heap em tempo linear. Por predefinição, o maior elemento fica no início; um comparador personalizado permite criar um heap mínimo. Não há garantia de que o intervalo resultante esteja ordenado.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#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 em <algorithm>, transforma [first, last) num heap, reorganizando os seus elementos e devolvendo void. O intervalo não tem de ser já um heap. A comparação predefinida cria um heap máximo: num intervalo não vazio, *first é o maior elemento. Isto não ordena o intervalo inteiro; a disposição exata dos restantes elementos não está especificada.

A sobrecarga que recebe comp cria um heap de acordo com esse comparador. Para cada filho, comp(parent, child) tem de ser falso. std::greater<int>{} de <functional> produz um heap mínimo. O comparador tem de definir uma ordem fraca estrita; não uses <= em vez de <.

São necessários iteradores de acesso aleatório, e os elementos têm de permitir troca, construção por movimento e atribuição por movimento. Para N = last - first, o algoritmo executa, no máximo, 3 * N comparações, pelo que a complexidade em comparações é linear. Um intervalo vazio é válido, mas nesse caso não deves ler *first nem front().

O exemplo verifica a raiz e a propriedade de heap, em vez de pressupor uma disposição específica de todos os elementos. Mantém a mesma ordenação nas operações seguintes: std::push_heap, std::pop_heap e std::sort_heap têm de usar um comparador compatível. std::pop_heap, por si só, não remove um elemento do contentor.

Exemplos

#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

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