sort_heap
Convertit un tas en une plage triée.
template<class RandomAccessIterator>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class Predicate>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
Predicate _Comp
);
Paramètres
_First
Itérateur à accès aléatoire se rapportant à la position du premier élément dans le tas cible._Last
Itérateur à accès aléatoire se rapportant à la position située immédiatement après l'élément final dans le tas cible._Comp
Objet de fonction de prédicat défini par l'utilisateur qui définit le sens dans lequel un élément est inférieur à un autre. Un prédicat binaire a besoin de deux arguments. Il renvoie true lorsqu'il est satisfait et false dans le cas contraire.
Notes
Les tas ont deux propriétés :
Le premier élément est toujours le plus grand.
Les éléments peuvent être ajoutés ou supprimés en un temps logarithmique.
Une fois que l'application a utilisé cet algorithme, la plage à laquelle il a été appliqué n'est plus un tas.
Il ne s'agit pas d'un tri stable, car l'ordre relatif des éléments équivalent n'est pas nécessairement conservé.
Les tas constituent un moyen idéal pour implémenter des files de priorité et ils sont utilisés dans l'implémentation de l'adaptateur de conteneur classe de priority_queue Standard Template Library (STL).
La plage source triée référencée doit être valide ; tous les pointeurs doivent être deréférençables et, dans la séquence, la dernière position doit être accessible à partir de la première par incrémentation.
La complexité est au plus N log N, où N = (_Last – _First).
Exemple
// alg_sort_heap.cpp
// compile with: /EHsc
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
using namespace std;
void print(const string& s, const vector<int>& v) {
cout << s << ": ( ";
for (auto i = v.begin(); i != v.end(); ++i) {
cout << *i << " ";
}
cout << ")" << endl;
}
int main() {
vector<int> v;
for (int i = 1; i <= 9; ++i) {
v.push_back(i);
}
print("Initially", v);
random_shuffle(v.begin(), v.end());
print("After random_shuffle", v);
make_heap(v.begin(), v.end());
print(" After make_heap", v);
sort_heap(v.begin(), v.end());
print(" After sort_heap", v);
random_shuffle(v.begin(), v.end());
print(" After random_shuffle", v);
make_heap(v.begin(), v.end(), greater<int>());
print("After make_heap with greater<int>", v);
sort_heap(v.begin(), v.end(), greater<int>());
print("After sort_heap with greater<int>", v);
}
Résultat de l'exemple
Initially: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 9 2 7 3 1 6 8 4 5 )
After make_heap: ( 9 5 8 4 1 6 7 2 3 )
After sort_heap: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 5 8 3 1 2 9 7 6 4 )
After make_heap with greater<int>: ( 1 2 3 4 5 9 7 6 8 )
After sort_heap with greater<int>: ( 9 8 7 6 5 4 3 2 1 )
Configuration requise
En-tête : <algorithme>
Espace de noms : std