Namespaces
Variants

std:: sort_heap

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
sort_heap
(C++11)
(C++11)
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Défini dans l'en-tête <algorithm>
template < class RandomIt >
void sort_heap ( RandomIt first, RandomIt last ) ;
(1) (constexpr depuis C++20)
template < class RandomIt, class Compare >
void sort_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(2) (constexpr depuis C++20)

Convertit le heap [ first , last ) en une plage triée. La propriété de heap n'est plus maintenue.

1) Le tas est par rapport à operator < (until C++20) std:: less { } (since C++20) , et sera trié par rapport à operator < (until C++20) std:: less { } (since C++20) .
2) Le tas est relatif à comp , et sera trié par rapport à comp .

Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

  • [ first , last ) n'est pas un tas.
(jusqu'à C++11)
(depuis C++11)

Table des matières

Paramètres

first, last - la paire d'itérateurs définissant la plage du tas binaire des éléments à transformer en plage triée
comp - objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de Compare ) qui renvoie true si le premier argument est inférieur au second.

La signature de la fonction de comparaison doit être équivalente à ce qui suit :

bool cmp ( const Type1 & a, const Type2 & b ) ;

Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs du type (éventuellement const) Type1 et Type2 indépendamment de la catégorie de valeur (ainsi, Type1 & n'est pas autorisé , pas plus que Type1 sauf si pour Type1 un déplacement équivaut à une copie (depuis C++11) ).
Les types Type1 et Type2 doivent être tels qu'un objet de type RandomIt puisse être déréférencé puis implicitement converti vers ces deux types.

Exigences de type
-
RandomIt doit satisfaire aux exigences de LegacyRandomAccessIterator .
-
Compare doit satisfaire aux exigences de Compare .

Complexité

Étant donné N comme std:: distance ( first, last ) :

1) Au maximum 2N⋅log(N) comparaisons en utilisant operator < (jusqu'à C++20) std:: less { } (depuis C++20) .
2) Au maximum 2N⋅log(N) applications de la fonction de comparaison comp .

Implémentation possible

sort_heap (1) 
template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last)
{
    while (first != last)
        std::pop_heap(first, last--);
}
sort_heap (2) 
template<class RandomIt, class Compare>
void sort_heap(RandomIt first, RandomIt last, Compare comp)
{
    while (first != last)
        std::pop_heap(first, last--, comp);
}

Exemple

Exécuter ce code 
#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view fmt, const auto& v)
{
    for (std::cout << fmt; const auto &i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
    std::make_heap(v.begin(), v.end());
    println("after make_heap, v: ", v);
    std::sort_heap(v.begin(), v.end());
    println("after sort_heap, v: ", v);
}

Sortie : 

after make_heap, v: 9 4 5 1 1 3
after sort_heap, v: 1 1 3 4 5 9

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR Applicable à Comportement publié Comportement corrigé
LWG 2444 C++98 au plus N⋅log(N) comparaisons étaient autorisées augmenté à 2N⋅log(N)

Voir aussi

(C++11)
vérifie si la plage donnée est un tas maximum
(modèle de fonction)
(C++11)
trouve la plus grande sous-plage qui est un tas maximum
(modèle de fonction)
crée un tas maximum à partir d'une plage d'éléments
(modèle de fonction)
supprime le plus grand élément d'un tas maximum
(modèle de fonction)
ajoute un élément à un tas maximum
(modèle de fonction)
(C++20)
transforme un tas maximum en une plage d'éléments triés par ordre croissant
(objet fonction algorithme)