Predicate Versions of heap
Muestra cómo utilizar las versiones del predicado de la función de Montón STL en Visual C++.
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
)
Comentarios
[!NOTA]
La clase y los nombres de parámetro en el prototipo no coincide con la versión del archivo de encabezado.Algunos se han modificado para mejorar la legibilidad.
Un montón es una secuencia de elementos organizados como un árbol binario.cada elemento de la pila corresponde a un nodo de árbol.el primer valor en la secuencia [First.Last) es la raíz y está ordenada por el predicado.Por ejemplo, si el predicado es mayor, cada elemento de la pila cumple la siguiente instrucción: Cada elemento es mayor o igual que su elemento primario.El elemento más pequeño se almacena en la raíz, y todos los elementos secundarios contienen valores progresivamente más grandes.la función de make_heap convierte el intervalo [First.Last) en una pila.La función de sort_heap ordena una secuencia creada mediante la función de make_heap .la función de push_heap inserta un nuevo valor en la pila.La función de pop_heap cambia el primer y último elemento de la pila especificada por [First, Last) y, a continuación reduce la longitud de la secuencia por una antes de restablecer la propiedad de la pila.Las versiones de predicado de las funciones del montón utilizan la función de comparación para las comparaciones.
Ejemplo
// 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 ;
}
Requisitos
encabezado: <algoritmo>