heap
Muestra cómo utilizar las funciones de la biblioteca estándar de la plantilla (STL) de Montón en Visual C++.
template<class RandomAccessIterator> inline
void make_heap(
RandomAccessIterator First,
RandomAccessIterator Last
)
template<class RandomAccessIterator> inline
void sort_heap(
RandomAccessIterator First,
RandomAccessIterator Last
)
template<class RandomAccessIterator> inline
void push_heap(
RandomAccessIterator First,
RandomAccessIterator Last
)
template<class RandomAccessIterator> inline
void pop_heap(
RandomAccessIterator First,
RandomAccessIterator Last
)
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 es el valor más grande de la pila.Cada elemento de la pila cumple el siguiente: Cada elemento es menor o igual que su elemento primario.El elemento más grande se almacena en la raíz, y todos los elementos secundarios contienen valores progresivamente menores.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 nonpredicate de las funciones del montón utilizan operator< para las comparaciones.
Ejemplo
// heapfunc.cpp
// compile with: /EHsc
//
// 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 characters,
// 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()) ;
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()) ;
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 ;
//insert an element in the heap
Numbers.push_back(7) ;
push_heap(Numbers.begin(), Numbers.end()) ;
// you need to call make_heap to re-assert the
// heap property
make_heap(Numbers.begin(), Numbers.end()) ;
cout << "After calling push_heap and make_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()) ;
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 ;
}
Output
Numbers { 4 10 70 10 30 69 96 100 }
After calling make_heap
Numbers { 100 30 96 10 4 69 70 10 }
After calling sort_heap
Numbers { 4 10 10 30 69 70 96 100 }
After calling push_heap and make_heap
Numbers { 100 69 96 30 4 70 10 10 7 }
After calling pop_heap
Numbers { 96 69 70 30 4 7 10 10 100 }
Requisitos
encabezado: <algoritmo>