pop_heap
Entfernt das größte Element der Vorderseite eines Heaps dem folgenden im - ZuLAST-Position Bereich und bildet dann einen neuen Heap von den übrigen Elemente.
template<class RandomAccessIterator>
void pop_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void pop_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 Heap._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
Der pop_heap - Algorithmus ist das Gegenteil des Vorgangs, der vom push_heap Algorithmus ausgeführt wird, in dem ein Element am folgenden - ZuLAST-Position eines Bereichs wird einem Heap hinzugefügt, der aus den vorherigen Elementen im Bereich, im Fall besteht, wenn das Element, das dem Heap hinzugefügt größer ist, als die Elemente bereits im Heap befindet.
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_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;
}
Beispielausgabe
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 ).
Anforderungen
Header: <algorithm>
Namespace: std