Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

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.

Sources