Predicate Versions of heap

Veranschaulicht, wie die Prädikatversionen der Funktion Heap STL in Visual C++ verwendet.

template<class RandomAccessIterator, class Compare> inline
   void make_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void sort_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void push_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void pop_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )

Hinweise

Hinweis
Die Klasse/Parameternamen im Prototyp stimmen nicht mit der Version in der Headerdatei ab.Einige wurden geändert, um die Lesbarkeit zu verbessern.

Ein Heap ist eine Sequenz von Elementen, die z. B. eine binäre Struktur organisiert wird.Jeder Heap Element entspricht einem Strukturknoten.Der erste Wert in der Sequenz [First.Last) ist der Stamm und wurde durch das Prädikat geordnet.Wenn z. B. das Prädikat größer ist, stellt jedes Element im Heap die folgende Anweisung aus: Jedes Element ist größer als oder gleich sein übergeordnetes Element.Das kleinste Element wird im Stammverzeichnis gespeichert, und alle untergeordneten Elemente bleiben nach und nach größere Werte an.Die make_heap-Funktion konvertiert den Bereich [First.Last) in einen Heap.Die sort_heap-Funktion sortierungen eine Sequenz, die mit der make_heap-Funktion erstellt wurde.Die push_heap-Funktion fügt einen neuen Wert in den Heap ein.Die Funktion pop_heap lagert das erste und letzte Elemente im Heap aus, der durchFirst[angegeben wird, Last) und reduziert die Länge der Sequenz um eine Heap, bevor die Eigenschaft wiederhergestellt werden kann.Die Prädikatversionen der Heap Compare-Funktion verwenden die Funktionen für Vergleiche.

Beispiel

// heap_PVfunctions.cpp
// compile with: /EHsc
// Illustrates how to use the predicate versions
// of the make_heap, sort_heap, push_heap
// and pop_heap functions.
//
// Functions:
//
//    make_heap : Convert a sequence to a heap.
//    sort_heap : Sort a heap.
//    push_heap : Insert an element in a heap.
//    pop_heap  : Remove the top element from a heap.
//////////////////////////////////////////////////////////////////////

// disable warning C4786: symbol greater than 255 character,
// okay to ignore
#pragma warning(disable: 4786)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;


int main()
{
   const int VECTOR_SIZE = 8 ;

   // Define a template class vector of int
   typedef vector<int > IntVector ;

   //Define an iterator for template class vector of strings
   typedef IntVector::iterator IntVectorIt ;

   IntVector Numbers(VECTOR_SIZE) ;
   IntVectorIt it ;

   // Initialize vector Numbers
   Numbers[0] = 4 ;
   Numbers[1] = 10;
   Numbers[2] = 70 ;
   Numbers[3] = 10 ;
   Numbers[4] = 30 ;
   Numbers[5] = 69 ;
   Numbers[6] = 96 ;
   Numbers[7] = 100;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   // convert Numbers into a heap
   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling make_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   // sort the heapified sequence Numbers
   sort_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling sort_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   //insert an element in the heap
   Numbers.push_back(7) ;
   push_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling push_heap()\n" << endl;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   //remove the root element from the heap Numbers
   pop_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling pop_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;
}

Anforderungen

Header: <algorithm>

Siehe auch

Konzepte

Standardvorlagenbibliotheks-Beispiele

Last updated on 2013-03-15