Cola de prioridad de tuplas en C++ con ejemplos

Posted on by Rudeus Greyrat

cola de prioridad

Las colas de prioridad son un tipo de adaptadores de contenedores, específicamente diseñados de tal manera que el primer elemento de la cola es el mayor de todos los elementos de la cola y los elementos están en orden no creciente (por lo tanto, podemos ver que cada elemento de la cola tiene una prioridad {fija ordenar}).

Funciones asociadas a una cola de prioridad:

  • vacío(): esta función devuelve si la cola está vacía.
  • size(): Esta función devuelve el tamaño de la cola.
  • top(): Devuelve una referencia al elemento superior de la cola.
  • push(x): esta función agrega el elemento ‘ x ‘ al final de la cola.

tupla

Una tupla es un objeto que puede contener varios elementos. Los elementos pueden ser de diferentes tipos de datos. Los elementos de las tuplas se inicializan como argumentos en el orden en que se accederá a ellos.

Funciones asociadas a una tupla:

  • get(): get() se utiliza para acceder a los valores de la tupla y modificarlos, acepta el índice y el nombre de la tupla como argumentos para acceder a un elemento de la tupla en particular.
  • make_tuple(): make_tuple() se usa para asignar tupla con valores. Los valores pasados ​​deben estar en orden con los valores declarados en la tupla.

Este artículo se centra en cómo se puede usar la cola de prioridad de tuplas en C++. La cola de prioridad de tuplas puede ser bastante útil al diseñar estructuras de datos complejas.

Syntax 1: Max-heap priority queue of tuples:
priority_queue<tuple<data_type1, data_type2, data_type3>> priorityQueue;

Syntax 2: Min-heap priority queue of tuples:
priority_queue<tuple<data_type1, data_type2, data_type3>, 
vector<tuple<data_type1, data_type2, data_type3>>, 
greater<tuple<data_type1, data_type2, data_type3>>> priorityQueue;

Syntax 3: Customized priority queue of tuples (using comparator):
priority_queue<tuple<data_type1, data_type2, data_type3>, 
vector<tuple<data_type1, data_type2, data_type3>>, comparator> priorityQueue;

Cola de tuplas de prioridad de pila máxima:

Por defecto, las colas de prioridad son max-heap. Entonces, en el caso de un par de tuplas en la cola de prioridad, se compara su primer elemento, y si el primer elemento de ambas tuplas es igual, entonces se compara su segundo elemento y si el segundo elemento también es igual, entonces el tercer elemento es comparado. La tupla que tiene el elemento más grande se convierte en el elemento superior de la cola de prioridad.  

Ejemplo 1: a continuación se muestra el programa C++ para implementar colas de tuplas con prioridad máxima de almacenamiento dinámico.

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority 
// queue
void print(priority_queue<tuple<int, 
           int, char> > priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // Each element of the priority
    // queue is a tuple itself
    tuple<int, int, char> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' << 
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // Pop out the topmost tuple
    priorityQueue.pop();
  }
}
  
// Driver code
int main()
{
  // Declaring a priority queue of
  // tuple
  priority_queue<tuple<int, int, 
  char> > priorityQueue;
  
  // Declaring a tuple
  tuple<int, int, char> tuple1;
  
  // Initializing the tuple
  tuple1 = make_tuple(1, 1, 'G');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple1);
  
  // Declaring another tuple
  tuple<int, int, char> tuple2;
  
  // Initializing the tuple
  tuple2 = make_tuple(2, 2, 'e');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple2);
  
  // Declaring another tuple
  tuple<int, int, char> tuple3;
  
  // Initializing the tuple
  tuple3 = make_tuple(3, 3, 'e');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple3);
  
  // Declaring another tuple
  tuple<int, int, char> tuple4;
  
  // Initializing the tuple
  tuple4 = make_tuple(4, 4, 'k');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple4);
  
  // Calling print function
  print(priorityQueue);
  
  return 0;
}
Producción

[ 4 4 k]
[ 3 3 e]
[ 2 2 e]
[ 1 1 G]

Ejemplo 2: a continuación se muestra el programa C++ para demostrar el funcionamiento de la cola de tuplas de prioridad máxima del montón.

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority 
// queue
void print(priority_queue<tuple<int, int, 
           string> > priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // Each element of the priority
    // queue is a tuple itself
    tuple<int, int, string> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' << 
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // Pop out the topmost tuple
    priorityQueue.pop();
  }
}
  
// Driver code
int main()
{
  // Declaring a priority queue
  // of tuple
  priority_queue<tuple<int, int, 
  string> > priorityQueue;
  
  // Declaring a tuple
  tuple<int, int, string> tuple1;
  
  // Initializing the tuple
  tuple1 = make_tuple(0, 0, "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple1);
  
  // Declaring a tuple
  tuple<int, int, string> tuple2;
  
  // Initializing the tuple
  tuple2 = make_tuple(0, 0, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple2);
  
  // Declaring a tuple
  tuple<int, int, string> tuple3;
  
  // Initializing the tuple
  tuple3 = make_tuple(1, 2, 
                      "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple3);
  
  // Declaring a tuple
  tuple<int, int, string> tuple4;
  
  // Initializing the tuple
  tuple4 = make_tuple(1, 3, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple4);
  
  // Calling print function
  print(priorityQueue);
  
  return 0;
}
Producción

[ 1 3 Programming]
[ 1 2 Geeks]
[ 0 0 Programming]
[ 0 0 Geeks]

Cola de prioridad de montón mínimo de tuplas:

En el caso de un par de tuplas en la cola de prioridad min-heap, se compara su primer elemento, y si el primer elemento de ambas tuplas es igual, entonces se compara su segundo elemento y si el segundo elemento también es igual, entonces el tercer elemento se compara. La tupla que tiene el elemento más pequeño se convierte en el elemento superior de la cola de prioridad.  

Ejemplo 1: a continuación se muestra el programa C++ para implementar el funcionamiento de la cola de tuplas de prioridad min-heap.

C++

// C++ program to implement 
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority 
// queue
void print(priority_queue<tuple<int, int, char>,
           vector<tuple<int, int, char> >,
           greater<tuple<int, int, char> > >
           priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // Each element of the priority
    // queue is a tuple itself
    tuple<int, int, char> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' << 
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // Pop out the topmost tuple
    priorityQueue.pop();
  }
}
  
// Driver code
int main()
{
  // Declaring a min-heap priority 
  // queue of tuple
  priority_queue<tuple<int, int, char>,
  vector<tuple<int, int, char> >,
  greater<tuple<int, int, char> > >
          priorityQueue;
  
  // Declaring a tuple
  tuple<int, int, char> tuple1;
  
  // Initializing the tuple
  tuple1 = make_tuple(1, 1, 'G');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple1);
  
  // Declaring another tuple
  tuple<int, int, char> tuple2;
  
  // Initializing the tuple
  tuple2 = make_tuple(2, 2, 'e');
  
  // pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple2);
  
  // Declaring another tuple
  tuple<int, int, char> tuple3;
  
  // Initializing the tuple
  tuple3 = make_tuple(3, 3, 'e');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple3);
  
  // Declaring another tuple
  tuple<int, int, char> tuple4;
  
  // Initializing the tuple
  tuple4 = make_tuple(4, 4, 'k');
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple4);
  
  // Calling print function
  print(priorityQueue);
  
  return 0;
}
Producción

[ 1 1 G]
[ 2 2 e]
[ 3 3 e]
[ 4 4 k]

Ejemplo 2: a continuación se muestra el programa C++ para implementar el funcionamiento de la cola de tuplas de prioridad min-heap.

C++

// C++ program to implement 
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority 
// queue
void print(priority_queue<tuple<int, int, string>,
           vector<tuple<int, int, string> >,
           greater<tuple<int, int, string> > >
           priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // Each element of the priority
    // queue is a tuple itself
    tuple<int, int, string> Tuple =
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' <<
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // Pop out the topmost tuple
    priorityQueue.pop();
  }
}
  
// Driver code
int main()
{
  // Declaring a priority queue of
  // tuple
  priority_queue<tuple<int, int, string>,
  vector<tuple<int, int, string> >,
  greater<tuple<int, int, string> > >
          priorityQueue;
  
  // Declaring a tuple
  tuple<int, int, string> tuple1;
  
  // Initializing the tuple
  tuple1 = make_tuple(0, 0, "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple1);
  
  // Declaring a tuple
  tuple<int, int, string> tuple2;
  
  // Initializing the tuple
  tuple2 = make_tuple(0, 0, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple2);
  
  // Declaring a tuple
  tuple<int, int, string> tuple3;
  
  // Initializing the tuple
  tuple3 = make_tuple(1, 2, 
                      "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple3);
  
  // Declaring a tuple
  tuple<int, int, string> tuple4;
  
  // Initializing the tuple
  tuple4 = make_tuple(1, 3, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple4);
  
  // Calling print function
  print(priorityQueue);
  
  return 0;
}
Producción

[ 0 0 Geeks]
[ 0 0 Programming]
[ 1 2 Geeks]
[ 1 3 Programming]

Cola de prioridad personalizada de tuplas:

Continuando ¿Cómo implementar Min Heap usando STL?  es un requisito previo obligatorio para ir donde aquí aprenderemos cómo podemos personalizar la cola de prioridad de tuplas pasando un comparador a la cola de prioridad como argumento.

Ejemplo 1: a continuación se muestra el programa C++ para implementar la cola de prioridad personalizada de tuplas.

C++

// C++ program to implement 
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Comparator
// we can use class also but then 
// we will need to make the function 
// public as class is by default 
// private
struct myComparator 
{
  int operator()(const tuple<int, int, 
                 string>& tuple1,
                 const tuple<int, int, 
                 string>& tuple2)
  {
    // Second element of tuples is equal
    if (get<1>(tuple1) == get<1>(tuple2)) 
    {
      if (get<0>(tuple1) == get<0>(tuple2)) 
      {
        if (get<2>(tuple1) >= get<2>(tuple2))
          return true;
        return false;
      }
  
      return get<0>(tuple1) >= get<0>(tuple2);
    }
  
    return get<1>(tuple1) >= get<1>(tuple2);
  }
};
  
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority 
// queue
void print(priority_queue<tuple<int, int, 
           string>,
           vector<tuple<int, int, 
           string> >,
           myComparator>
           priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // Each element of the priority
    // queue is a tuple itself
    tuple<int, int, string> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' <<
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // Pop out the topmost tuple
    priorityQueue.pop();
  }
}
  
// Driver code
int main()
{
  // Declaring a priority queue 
  // of  tuple
  priority_queue<tuple<int, int, string>,
  vector<tuple<int, int, string> >,
  myComparator> priorityQueue;
  
  // Declaring a tuple
  tuple<int, int, string> tuple1;
  
  // Initializing the tuple
  tuple1 = make_tuple(0, 0, 
                      "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple1);
  
  // Declaring a tuple
  tuple<int, int, string> tuple2;
  
  // Initializing the tuple
  tuple2 = make_tuple(0, 1, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple2);
  
  // Declaring a tuple
  tuple<int, int, string> tuple3;
  
  // Initializing the tuple
  tuple3 = make_tuple(1, 2, 
                      "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple3);
  
  // Declaring a tuple
  tuple<int, int, string> tuple4;
  
  // Initializing the tuple
  tuple4 = make_tuple(1, 3, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple4);
  
  // Calling print function
  print(priorityQueue);
  
  return 0;
}
Producción

[ 0 0 Geeks]
[ 0 1 Programming]
[ 1 2 Geeks]
[ 1 3 Programming]

En el programa anterior, para un par de tuplas, primero se compara el segundo elemento de las tuplas y si este valor es igual, se compara el primer elemento y si el primer elemento de ambas tuplas es igual, se compara el tercer elemento. De lo contrario, la tupla que tenga un elemento más pequeño se convertirá en el elemento superior.  

Ejemplo 2: a continuación se muestra el programa C++ para demostrar el funcionamiento de la cola de prioridad personalizada de tuplas.

C++

// C++ program to implement 
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Comparator
// we can use class also but then 
// we will need to make the function
// public as class is by default private
struct myComparator 
{
  int operator()(const tuple<int, int, 
                 string>& tuple1,
                 const tuple<int, int, 
                 string>& tuple2)
  {
    // Second element of tuples is equal
    if (get<1>(tuple1) == get<1>(tuple2)) 
    {
      // first element of tuples is equal
      if (get<0>(tuple1) == get<0>(tuple2)) 
      {
        if (get<2>(tuple1) <= get<2>(tuple2))
          return true;
        return false;
      }
  
      return get<0>(tuple1) <= get<0>(tuple2);
    }
  
    return get<1>(tuple1) <= get<1>(tuple2);
  }
};
  
// Function to print priority queue
// contents. Deliberately passing it
// call by value since we don't want
// to remove elements from the priority 
// queue
void print(priority_queue<tuple<int, int, 
           string>,
           vector<tuple<int, int, string> >,
           myComparator> priorityQueue)
{
  while (!priorityQueue.empty()) 
  {
    // Each element of the priority
    // queue is a tuple itself
    tuple<int, int, string> Tuple = 
          priorityQueue.top();
  
    cout << "[ ";
  
    cout << get<0>(Tuple) << ' ' << 
            get<1>(Tuple) << ' ' << 
            get<2>(Tuple);
    cout << ']';
    cout << '\n';
  
    // Pop out the topmost tuple
    priorityQueue.pop();
  }
}
  
// Driver code
int main()
{
  // Declaring a priority queue of
  // tuples by passing a custom comparator
  priority_queue<tuple<int, int, string>,
  vector<tuple<int, int, string> >,
  myComparator>
    priorityQueue;
  
  // Declaring a tuple
  tuple<int, int, string> tuple1;
  
  // Initializing the tuple
  tuple1 = make_tuple(0, 0, 
                      "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple1);
  
  // Declaring a tuple
  tuple<int, int, string> tuple2;
  
  // Initializing the tuple
  tuple2 = make_tuple(0, 1, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple2);
  
  // Declaring a tuple
  tuple<int, int, string> tuple3;
  
  // Initializing the tuple
  tuple3 = make_tuple(1, 2, 
                      "Geeks");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple3);
  
  // Declaring a tuple
  tuple<int, int, string> tuple4;
  
  // Initializing the tuple
  tuple4 = make_tuple(1, 3, 
                      "Programming");
  
  // Pushing the tuple in the 
  // priority queue
  priorityQueue.push(tuple4);
  
  // Calling print function
  print(priorityQueue);
  
  return 0;
}
Producción

[ 1 3 Programming]
[ 1 2 Geeks]
[ 0 1 Programming]
[ 0 0 Geeks]

En el programa anterior, para un par de tuplas, primero se compara el segundo elemento de las tuplas y si este valor es igual, se compara el primer elemento y si el primer elemento de ambas tuplas es igual, se compara el tercer elemento. De lo contrario, la tupla que tenga un elemento más grande se convertirá en el elemento superior.  

Publicación traducida automáticamente

Artículo escrito por bhuwanesh 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 *