¿Cómo implementar Min Heap usando STL?

En C++ STL, hay prioridad_cola que se puede usar directamente para implementar Max Heap. Para comprender completamente el código, asegúrese de estar familiarizado con los siguientes conceptos en C++ 

• Adaptadores de contenedores en STL
• Funtores

Vea el siguiente ejemplo:

// C++ program to show that priority_queue is by
// default a Max Heap
#include <bits/stdc++.h>
using namespace std;
  
// Driver code
int main ()
{
    // Creates a max heap
    priority_queue <int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(10);
    pq.push(30);
    pq.push(20);
  
    // One by one extract items from max heap
    while (pq.empty() == false)
    {
        cout << pq.top() << " ";
        pq.pop();
    }
  
    return 0;
}

30 20 10 5 1 

 
Dado que los elementos se imprimen en orden descendente, tenemos un montón máximo por defecto.
 
¿Cómo implementar Min Heap?  
Priority_queue admite un constructor que requiere dos argumentos adicionales para convertirlo en un montón mínimo. 

priority_queue <Type, vector<Type>, ComparisonType > min_heap;

`El tercer parámetro, ‘Tipo de comparación’, puede ser una función o un factor (también conocido como objeto de función) que debe tener bool como tipo de retorno y debe tener 2 argumentos.

A continuación se muestra un ejemplo de números enteros.

// C++ program to use priority_queue to implement min heap
#include <bits/stdc++.h>
using namespace std;
  
// Driver code
int main ()
{
    // Creates a min heap
    priority_queue <int, vector<int>, greater<int> > pq;
    pq.push(5);
    pq.push(1);
    pq.push(10);
    pq.push(30);
    pq.push(20);
  
    // One by one extract items from min heap
    while (pq.empty() == false)
    {
        cout << pq.top() << " ";
        pq.pop();
    }
  
    return 0;
}

Producción: 

1 5 10 20 30 

Otro método para hacer un montón mínimo usando la cola de prioridad predeterminada:

Esto se usa con frecuencia en la programación competitiva. Primero multiplicamos todos los elementos con (-1). Luego creamos un montón máximo (el montón máximo es el predeterminado para la cola de prioridad). Cuando accedemos a los datos y queremos imprimirlos simplemente multiplicamos esos elementos por (-1) de nuevo.

A continuación se muestra la implementación de la idea anterior:

// C++ Program to implement min heap
// using default priority_queue(max-heap)
  
#include <iostream>
#include <queue>
using namespace std;
  
int main()
{
    // data
    int arr[] = { 25, 7, 9, 15, 20, 36, 50 };
    
      // default priority_queue using max-heap
    priority_queue<int> pq;
    
      // size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // multiply -1 with all elements while
    // inserting
    for (int i = 0; i < n; i++) {
        pq.push((-1) * arr[i]);
    }
  
    // multiply all elements with -1 while
    // retrieve the elements
    while (!pq.empty()) {
        cout << (pq.top()) * (-1) << " ";
        pq.pop();
    }
  
    return 0;
}

7 9 15 20 25 36 50 

¿Cómo hacer un montón mínimo de clase definida por el usuario? 

Consideremos el siguiente ejemplo donde construimos un montón mínimo de 2 puntos D ordenados por el eje X.

// C++ program to use priority_queue to implement Min Heap
// for user defined class
#include <bits/stdc++.h>
using namespace std;
  
// User defined class, Point
class Point
{
   int x;
   int y;
public:
   Point(int x, int y)
   {
      this->x = x;
      this->y = y;
   }
   int getX() const { return x; }
   int getY() const { return y; }
};
  
// To compare two points
class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX() > p2.getX();
    }
};
  
// Driver code
int main ()
{
    // Creates a Min heap of points (order by x coordinate)
    priority_queue <Point, vector<Point>, myComparator > pq;
  
    // Insert points into the min heap
    pq.push(Point(10, 2));
    pq.push(Point(2, 1));
    pq.push(Point(1, 5));
  
    // One by one extract items from min heap
    while (pq.empty() == false)
    {
        Point p = pq.top();
        cout << "(" << p.getX() << ", " << p.getY() << ")";
        cout << endl;
        pq.pop();
    }
  
    return 0;
}

Producción: 

(1, 5)
(2, 1)
(10, 2)

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.