push_heap
Aggiunge un elemento che si trova alla fine di un intervallo a un heap esistente che include gli elementi precedenti nell'intervallo.
template<class RandomAccessIterator>
void push_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void push_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp
);
Parametri
_First
Un iteratore di accesso casuale destinato alla posizione del primo elemento nell'heap._Last
Un iteratore di accesso casuale destinato alla posizione una dopo l'elemento finale nell'intervallo da convertire in un heap._Comp
Oggetto definito dall'utente di funzione predicativa in cui viene definito il concetto cui è minore di un'altra.Un predicato binario accetta due argomenti e restituisce true una volta soddisfatti e false una volta non soddisfatta.
Note
L'elemento deve prima essere inserito alla fine di un heap esistente e l'algoritmo utilizzato per aggiungere questo elemento all'heap esistente.
Gli heap sono due proprietà:
Il primo elemento è sempre il più grande.
Gli elementi possono essere aggiunti o rimossi nel tempo logaritmico.
Gli heap sono modo ideale per implementare le code di priorità e utilizzate nell'implementazione dell'adattatore standard classe di priority_queuedella libreria di modelli.
l'intervallo fatto riferimento deve essere valido; tutti i puntatori devono essere dereferenceable e all'interno della sequenza dell'ultima posizione è raggiungibile da prima dall'aumento.
L'intervallo all'elemento appena aggiunto alla fine deve essere un heap.
Complessità è logaritmica, richiedendo al massimo i confronti del registro*_Last (– _First*).
Esempio
// 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;
}
Esempio di output
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 ).
Requisiti
intestazione: <algorithm>
Spazio dei nomi: deviazione standard