push_heap
Ajoute un élément qui correspond à la fin d'une plage à un tas existant qui se compose des éléments antérieurs dans l'intervalle.
template<class RandomAccessIterator>
void push_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void push_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 du 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
L'élément doit d'abord être de type push vers la fin d'un tas existant et l'algorithme est utilisé pour ajouter cet élément vers le tas existant.
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).
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.
L'intervalle à l'exclusion de l'élément récemment ajouté à la fin doit être un tas.
La complexité est logarithmique, lui demandant au plus de comparaison de journal (_Last – _First).
Exemple
// alg_push_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 = 1 ; 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;
// Add an element to the heap
v1.push_back( 10 );
cout << "The heap v1 with 10 pushed back is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
push_heap( v1.begin( ), v1.end( ) );
cout << "The reheaped v1 with 10 added is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl << 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\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
v1.push_back(0);
cout << "The greater-than heap v1 with 11 pushed back is\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
push_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The greater than reheaped v1 with 11 added is\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
Résultat de l'exemple
Vector v1 is ( 9 2 7 3 1 6 8 4 5 ).
The heaped version of vector v1 is ( 9 5 8 4 1 6 7 2 3 ).
The heap v1 with 10 pushed back is ( 9 5 8 4 1 6 7 2 3 10 ).
The reheaped v1 with 10 added is ( 10 9 8 4 5 6 7 2 3 1 ).
The greater-than heaped version of v1 is
( 1 2 6 3 5 8 7 4 10 9 ).
The greater-than heap v1 with 11 pushed back is
( 1 2 6 3 5 8 7 4 10 9 0 ).
The greater than reheaped v1 with 11 added is
( 0 1 6 3 2 8 7 4 10 9 5 ).
Configuration requise
en-tête : <algorithm>
l'espace de noms : DST