push_heap
Ajoute un élément qui se trouve à la fin d'une plage à un tas existant, constitué des éléments précédents de la plage.
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
Itérateur à accès aléatoire se rapportant à la position du premier élément dans le tas._Last
Un itérateur à accès aléatoire qui adresse la position située un cran après l'élément final dans la plage à convertir en tas._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
L'élément doit d'abord être envoyés vers la fin d'un tas existant et l'algorithme permet d'ajouter l'élément au 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 en un temps logarithmique.
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 plage à l'exception de l'élément récemment ajouté à la fin doit être un tas.
La complexité est logarithmique, exigeant au maximum les comparaisons log (_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 : <algorithme>
Espace de noms : std