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

CKTIS / C++

std::make_heap — construire un tas à partir d’une plage

std::make_heap réorganise une plage pour en faire un tas en temps linéaire. Par défaut, le plus grand élément est placé au début ; un comparateur personnalisé permet de créer un tas-min. Rien ne garantit que la plage obtenue soit triée.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

#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 std

std::make_heap, déclaré dans <algorithm>, transforme [first, last) en tas, en réorganisant ses éléments, et renvoie void. La plage n’a pas besoin d’être déjà un tas. La comparaison par défaut crée un tas-max : pour une plage non vide, *first est l’élément le plus grand. Cela ne trie pas toute la plage ; l’agencement exact des autres éléments n’est pas spécifié.

La surcharge qui prend comp construit un tas selon ce comparateur. Pour chaque enfant, comp(parent, child) doit être faux. std::greater<int>{} de <functional> produit un tas-min. Le comparateur doit définir un ordre faible strict ; n’utilisez pas <= à la place de <.

Des itérateurs à accès aléatoire sont requis, et les éléments doivent pouvoir être échangés, construits par déplacement et affectés par déplacement. Pour N = last - first, l’algorithme effectue au plus 3 * N comparaisons : la complexité en nombre de comparaisons est donc linéaire. Une plage vide est valide, mais il ne faut alors lire ni *first ni front().

L’exemple vérifie la racine et la propriété de tas plutôt que de supposer un agencement particulier de tous les éléments. Conservez le même ordre dans les opérations suivantes : std::push_heap, std::pop_heap et std::sort_heap doivent utiliser un comparateur compatible. std::pop_heap seul ne retire pas d’élément du conteneur.

Exemples

#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';
}

Résultat

max: 7
heap: true
min: 1

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