pop_heap
Retire le plus grand élément du début du tas et le place à l'avant-dernière position de la plage, puis forme un nouveau tas à partir des éléments restants.
template<class RandomAccessIterator>
void pop_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void pop_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
Itérateur à accès aléatoire se rapportant à la position située immédiatement après l'élément final dans le 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'algorithme pop_heap est l'inverse de l'opération effectuée par l'algorithme push_heap, dans lequel un élément à la position suivant dernière position d'une plage est ajouté à un tas comprenant les éléments antérieurs de la plage, dans le cas où l'élément est ajouté au segment de mémoire est supérieur à tout élément déjà dans le tas.
Les tasont 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.
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_pop_heap.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
v1.push_back( i );
// Make v1 a heap with default less than ordering
random_shuffle( v1.begin( ), v1.end( ) );
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 back of the heap
v1.push_back( 10 );
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;
// Remove the largest element from the heap
pop_heap( v1.begin( ), v1.end( ) );
cout << "The heap v1 with 10 removed is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl << endl;
// Make v1 a heap with greater-than ordering with a 0 element
make_heap ( v1.begin( ), v1.end( ), greater<int>( ) );
v1.push_back( 0 );
push_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The 'greater than' reheaped v1 puts the smallest "
<< "element first:\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Application of pop_heap to remove the smallest element
pop_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The 'greater than' heaped v1 with the smallest element\n "
<< "removed from the heap is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
Résultat de l'exemple
The heaped version of vector v1 is ( 9 5 8 4 1 6 7 2 3 ).
The reheaped v1 with 10 added is ( 10 9 8 4 5 6 7 2 3 1 ).
The heap v1 with 10 removed is ( 9 5 8 4 1 6 7 2 3 10 ).
The 'greater than' reheaped v1 puts the smallest element first:
( 0 1 6 3 2 8 7 4 9 10 5 ).
The 'greater than' heaped v1 with the smallest element
removed from the heap is: ( 1 2 6 3 5 8 7 4 9 10 0 ).
Configuration requise
En-tête : <algorithme>
Espace de noms : std