make_heap() en C++ STL – Part 1

make_heap() se usa para transformar una secuencia en un montón. Un montón es una estructura de datos que apunta al elemento más alto (o más bajo) y hace su acceso en tiempo O (1) . El orden de todos los demás elementos depende de la implementación particular, pero se mantiene constante en todo momento. Esta función se define en el encabezado » algoritmo «. Hay dos implementaciones de la función make_heap(). Ambos se explican a través de este artículo. 

Sintaxis 1: make_heap(iter_first, iter_last)

Plantilla: void make_heap (RandomAccessIterator primero, RandomAccessIterator último); Parámetros: primero : el puntero al elemento inicial de la secuencia que debe transformarse en un montón. last : el puntero a la siguiente dirección del último elemento de la secuencia que debe transformarse en un montón.

A continuación se muestra el código de demostración:

// C++ code to demonstrate the working of
// make_heap() using syntax 1
 
#include<iostream>
#include<algorithm> // for heap
#include<vector>
using namespace std;
 
int main()
{
    // initializing vector;
    vector<int> vi = { 4, 6, 7, 9, 11, 4 };
     
    // using make_heap() to transform vector into
    // a max heap
    make_heap(vi.begin(),vi.end());
     
    //checking if heap using
    // front() function
    cout << "The maximum element of heap is : ";
    cout << vi.front() << endl;
     
}

The maximum element of heap is : 11

Sintaxis 2: make_heap(iter_first, iter_last, comp)

Plantilla: void make_heap (RandomAccessIterator primero, RandomAccessIterator último, borrador); Parámetros: primero : el puntero al elemento inicial de la secuencia que debe transformarse en un montón. last : el puntero a la siguiente dirección del último elemento de la secuencia que debe transformarse en un montón. comp: la función de comparación que devuelve un valor booleano verdadero/falso de cada uno de los elementos comparados. Esta función acepta dos argumentos. Puede ser un puntero de función o un objeto de función y no puede cambiar los valores.

A continuación se muestra el código de demostración:

// C++ code to demonstrate the working of
// make_heap() using syntax 2
 
#include<iostream>
#include<algorithm> // for heap
#include<vector>
using namespace std;
 
// comparator function to make min heap
struct greaters{
bool operator()(const long& a,const long& b) const{
    return a>b;
}
};
 
int main()
{
    // initializing vector;
    vector<int> vi = { 15, 6, 7, 9, 11, 45 };
     
    // using make_heap() to transform vector into
    // a min heap
    make_heap(vi.begin(),vi.end(), greaters());
     
    // checking if heap using
    // front() function
    cout << "The minimum element of heap is : ";
    cout << vi.front() << endl;
     
}

The minimum element of heap is : 6

Posible aplicación: esta función se puede utilizar en la programación. En la programación, un nuevo elemento se inserta dinámicamente en las iteraciones. Ordenar una y otra vez para obtener el máximo requiere mucha complejidad O (nlogn), en lugar de eso, usamos la función «push_heap()» para acumular el montón creado en el tiempo O (logn). El siguiente código muestra su implementación. 

Implementación:

// C++ code to demonstrate
// application of make_heap() (max_heap)
// priority scheduling
 
#include<iostream>
#include<algorithm> // for heap
#include<vector>
using namespace std;
 
int main()
{
    // initializing vector;
    // initial job priorities
    vector<int> vi = { 15, 6, 7, 9, 11, 19};
     
    // No. of incoming jobs.
    int k = 3;
     
    // using make_heap() to transform vector into
    // a min heap
    make_heap(vi.begin(),vi.end());
     
    // initializing job variable
    int a = 10;
     
    for ( int i=0; i<k; i++)
    {
     
    // push a job with priority level
    vi.push_back(a);
     
    // transform into heap ( using push_heap() )
    push_heap(vi.begin(), vi.end());
     
    //checking top priority job
    // front() function
    cout << "Job with maximum priority is : ";
    cout << vi.front() << endl;
     
    // increasing job priority level
    a = a + 10;
     
    }
     
}

Job with maximum priority is : 19
Job with maximum priority is : 20
Job with maximum priority is : 30

Este artículo es una contribución de Manjeet Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.