Cola de prioridad de pares en C++ con ordenación por primer y segundo elemento

Cola de prioridad: la cola de prioridad es la extensión de la cola en la que los elementos asociados con la prioridad y los elementos que tienen mayor prioridad aparecen primero.

La cola de prioridad puede contener elementos con varios tipos de datos, como enteros, pares de enteros, tipos de datos personalizados. Pero una cosa es común que hay un elemento que define la prioridad del elemento.
Por lo tanto, la cola de prioridad de pares puede tener dos tipos de ordenación:

  • Ordenado por el primer elemento del par
  • Ordenado por el segundo elemento del par.

Cola de prioridad ordenada por primer elemento

En C++, si el elemento está en forma de pares, entonces, por defecto, la prioridad de los elementos depende del primer elemento. Por lo tanto, solo tenemos que usar la cola de prioridad de pares solamente.

C++

// C++ implementation of the
// priority queue of pairs
// ordered by the first element
  
#include <iostream>
#include <queue>
using namespace std;
  
// Function to print the data of
// the priority queue ordered by first
void showpq(
    priority_queue<pair<int, int> > g)
{
    // Loop to print the elements
    // until the priority queue
    // is not empty
    while (!g.empty()) {
        cout << g.top().first
             << " " << g.top().second
             << endl;
        g.pop();
    }
    cout << endl;
}
  
// Driver Code
int main()
{
    priority_queue<pair<int, int> > p1;
  
    // Insertion of elements
    p1.push(make_pair(4, 5));
    p1.push(make_pair(5, 4));
    p1.push(make_pair(1, 6));
    p1.push(make_pair(7, 3));
    p1.push(make_pair(9, 4));
    showpq(p1);
    return 0;
}
Producción:

9 4
7 3
5 4
4 5
1 6

Nota: Si el primer elemento de algunos pares es el mismo, la comparación se realizará sobre la base del segundo elemento.

Cola de prioridad ordenada por segundo elemento (Max)

La idea es utilizar estructura con el concepto de sobrecarga del operador en la cola de prioridad para ordenar los pares por su segundo elemento.

A continuación se muestra la implementación de la cola de prioridad ordenada por segundo elemento:

C++

// C++ implementation of the
// priority queue in which elements
// are sorted by the second element
  
#include <iostream>
#include <queue>
#include <vector>
  
using namespace std;
  
typedef pair<int, int> pd;
  
// Structure of the condition
// for sorting the pair by its
// second elements
struct myComp {
    constexpr bool operator()(
        pair<int, int> const& a,
        pair<int, int> const& b)
        const noexcept
    {
        return a.second < b.second;
    }
};
  
// Function to show the elements
// of the priority queue
void showpq(
    priority_queue<pd,
                   vector<pd>, myComp>
        g)
{
    // Loop to print the elements
    // until the priority queue
    // is not empty
    while (!g.empty()) {
        cout << g.top().first
             << " " << g.top().second
             << endl;
        g.pop();
    }
    cout << endl;
}
  
// Driver Code
int main()
{
    priority_queue<pd, vector<pd>, myComp> p1;
    p1.push(make_pair(4, 5));
    p1.push(make_pair(5, 4));
    p1.push(make_pair(1, 6));
    p1.push(make_pair(7, 3));
    p1.push(make_pair(9, 4));
  
    // Function Call
    showpq(p1);
    return 0;
}
Producción:

1 6
4 5
9 4
5 4
7 3

Cola de prioridad ordenada por segundo elemento (Min)

La idea es utilizar la sobrecarga del operador para implementar la cola de prioridad ordenada por su segundo elemento con el elemento mínimo en la parte superior.

A continuación se muestra la implementación de la cola de prioridad:

C++

// C++ implementation of the priority
// queue sorted by the second element
// in the decreasing order
  
#include <iostream>
#include <queue>
#include <vector>
  
using namespace std;
  
typedef pair<int, int> pd;
  
// Structure of the operator
// overloading for comparison
struct myComp {
    constexpr bool operator()(
        pair<int, int> const& a,
        pair<int, int> const& b)
        const noexcept
    {
        return a.second > b.second;
    }
};
  
// Function to print the elements
// of the priority queue
void showpq(
    priority_queue<pd, vector<pd>, myComp> g)
{
    // Loop to print the elements
    // of the priority queue
    while (!g.empty()) {
        cout << g.top().first
             << " " << g.top().second
             << endl;
        g.pop();
    }
    cout << endl;
}
  
// Driver Code
int main()
{
    priority_queue<pd, vector<pd>, myComp> p1;
  
    // Insertion of the elements
    p1.push(make_pair(4, 5));
    p1.push(make_pair(5, 4));
    p1.push(make_pair(1, 6));
    p1.push(make_pair(7, 3));
    p1.push(make_pair(9, 4));
    showpq(p1);
    return 0;
}
Producción:

7 3
5 4
9 4
4 5
1 6

Publicación traducida automáticamente

Artículo escrito por shivamtripathi91 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *