Freigeben über


make_heap

Konvertiert Elemente von einem angegebenen Bereichs in einen Heap, in dem das erste Element ist und für das Element, das ein Sortierungskriterium möglicherweise mit einem binären Prädikat angegeben wird.

template<class RandomAccessIterator> 
   void make_heap( 
      RandomAccessIterator _First,  
      RandomAccessIterator _Last 
   ); 
template<class RandomAccessIterator, class BinaryPredicate> 
   void make_heap( 
      RandomAccessIterator _First,  
      RandomAccessIterator _Last,
      BinaryPredicate _Comp 
   );

Parameter

  • _First
    Ein Iterator mit wahlfreier Zugriff, der die Position des ersten Elements im Bereich behandelt, in einen Heap konvertiert werden.

  • _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

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.

Die Komplexität ist linear und erfordert 3 * (_Last - _First), Vergleiche.

Beispiel

// alg_make_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 = 0 ; 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;

   // 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 ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;
}

Beispielausgabe

Vector v1 is ( 8 1 9 2 0 5 7 3 4 6 ).
The heaped version of vector v1 is ( 9 6 8 4 1 5 7 3 2 0 ).
The greater-than heaped version of v1 is ( 0 1 5 2 6 8 7 3 4 9 ).

Anforderungen

Header: <algorithm>

Namespace: std

Siehe auch

Referenz

heap

Standardvorlagenbibliothek