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