CKTIS / C++
std::push_heap — adicionar um elemento a um heap
std::push_heap restabelece a propriedade de heap depois de ser acrescentado um elemento ao fim de um intervalo. Não aumenta o tamanho do contentor: o novo elemento tem de estar já em last - 1 e a parte anterior do intervalo tem de ser um heap válido.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap, declarado em <algorithm>, incorpora o elemento em last - 1 no heap que abrange [first, last). Não acrescenta por si só elementos ao contentor e devolve void. A sequência habitual é chamar push_back e, em seguida, std::push_heap com os iteradores atualizados.
Antes da chamada, [first, last - 1) já tem de ser um heap segundo a mesma ordenação. O intervalo tem de conter pelo menos o novo elemento; não chame o algoritmo com um intervalo vazio. Para construir um heap a partir de dados arbitrários, utilize std::make_heap em vez de uma única chamada a std::push_heap.
A comparação predefinida produz um heap máximo: o elemento maior fica no início. A sobrecarga que recebe comp altera a ordenação; std::greater<int>{} produz um heap mínimo. O comparador tem de definir uma ordenação fraca estrita e ser compatível com a ordenação do heap existente. Um heap não tem de estar ordenado.
São necessários iteradores de acesso aleatório e elementos que suportem troca, construção por movimento e atribuição por movimento. O número de comparações é O(log N), em que N = last - first; o custo do push_back anterior é independente. No exemplo, {9, 5, 7} já é um heap, pelo que basta uma chamada depois de acrescentar 12 para restabelecer a propriedade de heap.
Exemplos
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> heap{9, 5, 7};
heap.push_back(12);
std::push_heap(heap.begin(), heap.end());
std::cout << "top: " << heap.front() << '\n';
std::cout << "size: " << heap.size() << '\n';
std::cout << "is_heap: " << std::boolalpha
<< std::is_heap(heap.begin(), heap.end()) << '\n';
}
Resultado
top: 12 size: 4 is_heap: true
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.