CKTIS / C++
std::pop_heap — déplacer la racine du tas à la fin
std::pop_heap déplace la racine d’un tas non vide à la fin de la plage et rétablit le tas dans le préfixe restant. Il ne supprime aucun élément du conteneur. Dans un std::vector, pop_back() ne supprime l’élément extrait que si la plage du tas s’étend jusqu’à la fin du vecteur.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::pop_heap(first, last);
std::pop_heap(first, last, comp);std::pop_heap, déclaré dans <algorithm>, agit sur [first, last). Il déplace la racine d’origine vers last - 1 et rétablit un tas dans [first, last - 1). Par défaut, la racine est le plus grand élément. La surcharge qui prend comp utilise l’ordre fourni ; les deux surcharges renvoient void.
La plage doit déjà être un tas non vide selon le même ordre. Les itérateurs doivent prendre en charge l’accès aléatoire, et les éléments doivent pouvoir être échangés, construits par déplacement et affectés par déplacement. Le comparateur doit définir un ordre faible strict. L’appel sur une plage vide ou sur une plage qui n’est pas un tas enfreint les préconditions.
L’algorithme ne réduit pas la taille du conteneur. Après l’appel, lisez l’élément extrait avec *(last - 1). Dans un std::vector, n’utilisez back() pour le lire et pop_back() pour le supprimer que si last est égal à l’itérateur end() du vecteur. Si la plage s’arrête avant, ces appels liraient et supprimeraient un autre élément. Avant un nouvel appel, excluez de la plage l’élément extrait précédemment. Le nombre de comparaisons est au plus 2 * log2(N), où N = last - first.
L’exemple construit un tas avec std::make_heap et affiche uniquement des résultats garantis, et non l’agencement interne du tas. Le code présenté a été exécuté sans modification, et sa sortie standard correspondait exactement à la sortie indiquée. La source est un projet de norme en évolution, et non le texte figé de C++23.
Exemples
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 7, 3};
std::make_heap(values.begin(), values.end());
std::pop_heap(values.begin(), values.end());
std::cout << "extracted=" << values.back() << '\n';
std::cout << "size_before=" << values.size() << '\n';
values.pop_back();
std::cout << "size_after=" << values.size() << '\n';
std::cout << "next=" << values.front() << '\n';
std::cout << "heap=" << std::boolalpha
<< std::is_heap(values.begin(), values.end()) << '\n';
}
Résultat
extracted=7 size_before=4 size_after=3 next=4 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.