make_heap
Convertit les éléments d'une plage spécifiée dans un tas dans lequel le premier élément est le plus grand et pour ce qu'un critère de tri peut être spécifié avec un attribut binaire.
template<class RandomAccessIterator>
void make_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void make_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp
);
Paramètres
_First
Un itérateur d'accès aléatoire adressant la position du premier élément dans la plage à convertir en un tas._Last
Un itérateur d'accès aléatoire adressant une position au delà de le dernier élément dans la plage à convertir en un tas._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.
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).
La complexité est linéaire, lui demandant 3 * (_Last – _First) des comparaisons.
Exemple
// alg_make_heap.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main() {
using namespace std;
vector <int> v1, v2;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 0 ; i <= 9 ; i++ )
v1.push_back( i );
random_shuffle( v1.begin( ), v1.end( ) );
cout << "Vector v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Make v1 a heap with default less than ordering
make_heap ( v1.begin( ), v1.end( ) );
cout << "The heaped version of vector v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Make v1 a heap with greater than ordering
make_heap ( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The greater-than heaped version of v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
Résultat de l'exemple
Vector v1 is ( 8 1 9 2 0 5 7 3 4 6 ).
The heaped version of vector v1 is ( 9 6 8 4 1 5 7 3 2 0 ).
The greater-than heaped version of v1 is ( 0 1 5 2 6 8 7 3 4 9 ).
Configuration requise
en-tête : <algorithm>
l'espace de noms : DST