make_heap
Convierte los elementos de un intervalo especificado en una pila del primer elemento es el mayor y para el que se puede especificar un criterio de ordenación con un predicado binario.
template<class RandomAccessIterator>
void make_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void make_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp
);
Parámetros
_First
Un iterador de acceso aleatorio que dirige la posición del primer elemento del intervalo que se convertirá en una pila._Last
Un iterador de acceso aleatorio que dirige la posición una más allá del último elemento en el intervalo que se convertirá en una pila._Comp
Objeto definido por el usuario de la función de predicado en el que define sentido que un elemento es menor que otro.Un predicado binario toma dos argumentos y devuelve TRUE cuando se cumple y Falso cuando no se cumple.
Comentarios
Los montones tienen dos propiedades:
El primer elemento es siempre el mayor.
los elementos se pueden agregar o quitar en tiempo logarítmico.
Las pilas son una forma ideal de implementar las colas de prioridad y se utilizan en la implementación del adaptador estándar clase priority_queuedel contenedor de la plantilla.
la complejidad es lineal, requiriendo 3 * (_Last – _First) las comparaciones.
Ejemplo
// 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;
}
Resultados del ejemplo
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 ).
Requisitos
encabezado: <algoritmo>
espacio de nombres: std