push_heap
Fügt ein Element hinzu, das am Ende eines Bereichs in einen vorhandenen Heap befindet, der aus den vorherigen Elementen im Bereich besteht.
template<class RandomAccessIterator>
void push_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void push_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp
);
Parameter
_First
Ein Iterator mit wahlfreier Zugriff, der die Position des ersten Elements im Heap._Last
Ein Iterator mit wahlfreier Zugriff, der die Position eine hinter dem letzten Element im Bereich behandelt, in einen Heap konvertiert werden._Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das den Sinn definiert, in dem ein Element kleiner als ein anderes ist. Ein binärer Prädikat akzeptiert zwei Argumente und gibt bei Erfüllung true zurück und false, wenn es nicht erfüllt wird.
Hinweise
Das Element muss wieder am Ende eines vorhandenen Heaps zuerst gedrückt werden und dann wird der Algorithmus verwendet, um dieses Element dem vorhandenen Heap hinzuzufügen.
Heaps haben zwei Eigenschaften:
Das erste Element ist immer der größte.
Elemente werden in der logarithmischen Zeit hinzugefügt oder entfernt werden.
Heaps sind eine ideale Möglichkeit, Prioritätswarteschlangen zu implementieren und sie sind in der Implementierung des Standardvorlagenbibliothekscontaineradapters priority_queue Klasse verwendet.
Der Bereich, auf den verwiesen wird, gültig sein; muss alle Zeiger müssen dereferenzierbar befinden der Sequenz ist die letzte Position der ersten von Zunahme erreichbar.
Der Bereich ausschließlich des hinzugefügten Elements am Ende muss ein Heap sein.
Die Komplexität ist logarithmisch und höchstens erfordert Vergleiche des Protokolls (_Last - _First).
Beispiel
// 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;
}
Beispielausgabe
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 ).
Anforderungen
Header: <algorithm>
Namespace: std