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

CKTIS / C++

std::sort_heap — trier un tas existant

std::sort_heap transforme un tas en une plage triée. La fonction exige des itérateurs à accès aléatoire et une plage qui constitue un tas valide selon la comparaison qu’elle utilise ; elle ne trie pas directement des données quelconques.

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

Syntaxe

#include <algorithm>

 template<class RandomAccessIterator>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

std::sort_heap, déclaré dans <algorithm>, trie sur place les éléments de [first, last) et renvoie void. La plage doit déjà constituer un tas valide selon la comparaison utilisée par std::sort_heap. Pour des données quelconques, appelez d’abord std::make_heap ou utilisez directement std::sort.

La surcharge sans comp produit un ordre non décroissant pour les nombres. Un comp personnalisé doit définir un ordre faible strict. Cet ordre n’a pas à être identique à celui qui a servi à construire le tas, pourvu que la plage constitue un tas valide selon comp. Par exemple, utiliser std::greater<int>{} à la fois dans std::make_heap et dans std::sort_heap produit un résultat non croissant. Passer une plage qui n’est pas un tas approprié viole une précondition.

Des itérateurs à accès aléatoire sont requis, et les éléments doivent satisfaire aux exigences de permutabilité, de construction par déplacement et d’affectation par déplacement. Pour N = last - first, l’algorithme effectue au plus 2 N log N comparaisons. La stabilité — la conservation de l’ordre des éléments équivalents selon la comparaison — n’est pas garantie. Le résultat est trié ; ne supposez pas qu’il reste un tas selon le même ordre.

L’exemple construit d’abord un tas à partir de cinq nombres, puis le trie pour obtenir 1 2 3 4 5. Cette fiche décrit les surcharges classiques de std::sort_heap, et non l’interface distincte std::ranges::sort_heap. La source est le projet actuel de la norme ; l’exemple est destiné à une vérification locale avec -std=c++23.

Exemples

#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>

int main() {
    std::array<int, 5> values{4, 1, 5, 2, 3};
    std::make_heap(values.begin(), values.end());
    std::sort_heap(values.begin(), values.end());

    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';
}

Résultat

1 2 3 4 5

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