sort_heap

Article
03/26/2013

Convertit un tas dans une plage trié.

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
Un itérateur d'accès aléatoire adressant la position du premier élément du tas cible.
_Last
Un itérateur d'accès aléatoire adressant une position au delà de le dernier élément dans le tas cible.
_Comp
Objet défini par l'utilisateur de fonction de prédicat dans lequel définit le sens celles l'élément est inférieur des autres.Un attribut binaire accepte deux arguments et retourne true si satisfaite et false une fois pas de contenu.

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 dans le temps logarithmique.

Après l'application si cet algorithme, l'intervalle il a été appliqué à n'est plus un tas.

Ce n'est pas un tri stable car la commande relative d'éléments équivalents n'est pas nécessairement conservé.

Les tas sont un moyen idéale pour implémenter des files d'attente de priorité et ils sont utilisés dans l'implémentation de l'adaptateur classe de priority_queuede conteneur Standard Template Library).

l'intervalle référencé doit être valide ; tous les pointeurs doivent être deréférençables et dans la séquence la dernière position est accessible dès le début par l'augmentation.

La complexité est au plus le journal NN , 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 : <algorithm>

l'espace de noms : DST

Voir aussi

Référence

heap

Modèles Standard

Partager via