CKTIS / C++
std::push_heap — ajouter un élément à un tas
std::push_heap rétablit la propriété de tas après l’ajout d’un élément à la fin d’une plage. Il n’agrandit pas le conteneur : le nouvel élément doit déjà se trouver à last - 1, et la partie précédente de la plage doit déjà être un tas valide.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap, déclaré dans <algorithm>, intègre l’élément situé à last - 1 au tas couvrant [first, last). Il n’ajoute pas lui-même d’élément au conteneur et renvoie void. La séquence habituelle consiste à appeler push_back, puis std::push_heap avec les itérateurs à jour.
Avant l’appel, [first, last - 1) doit déjà être un tas selon le même ordre. La plage doit contenir au moins le nouvel élément ; n’appelez pas l’algorithme sur une plage vide. Pour construire un tas à partir de données quelconques, utilisez std::make_heap plutôt qu’un unique appel à std::push_heap.
La comparaison par défaut produit un tas max : le plus grand élément se trouve au début. La surcharge qui prend comp modifie l’ordre ; std::greater<int>{} produit un tas min. Le comparateur doit définir un ordre faible strict et être cohérent avec l’ordre du tas existant. Un tas n’a pas besoin d’être trié.
Des itérateurs à accès aléatoire sont requis, ainsi que des éléments prenant en charge l’échange, la construction par déplacement et l’affectation par déplacement. Le nombre de comparaisons est O(log N), où N = last - first ; le coût de l’appel précédent à push_back est distinct. Dans l’exemple, {9, 5, 7} est déjà un tas ; après l’ajout de 12, un seul appel suffit donc à rétablir la propriété de tas.
Exemples
#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';
}
Résultat
top: 12 size: 4 is_heap: true
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.