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:
CPP
// 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:
CPP
// 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:
CPP
// 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA