Cola de prioridad de conjuntos en C++ con ejemplos

Colas de prioridad

Las colas de prioridad son un tipo de adaptadores de contenedores, diseñados específicamente de modo 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 utilizadas con colas de prioridad:

  • vacío(): devuelve si la cola está vacía.
  • size(): Devuelve el tamaño de la cola.
  • top(): Devuelve una referencia al elemento superior de la cola.
  • pop(): Elimina el primer elemento de la cola.

Conjuntos

Los conjuntos son un tipo de contenedor asociativo en el que cada elemento tiene que ser único porque el valor del elemento lo identifica.

Funciones utilizadas con Sets:

  • size(): Devuelve el número de elementos del conjunto.
  • insert(const x): Agrega un nuevo elemento ‘x’ al conjunto.

La cola de prioridad de conjuntos puede ser bastante útil para diseñar estructuras de datos complejas.

Sintaxis:

priority_queue<set<data_type>> priorityQueue 
This stores set as an element in the max-heap priority queue

A continuación se muestra la implementación de la cola de prioridad max-heap de set:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print priority
// queue contents
void print(priority_queue<set<int> > priorityQueue)
{
    while (!priorityQueue.empty()) {
        // Each element of the priority
        // queue is a set itself
        set<int> st = priorityQueue.top();
 
        cout << "[ ";
 
        // Print the set elements
        for (auto element : st)
            cout << element << ' ';
        cout << ']';
        cout << '\n';
 
        // Pop out the topmost set
        priorityQueue.pop();
    }
}
 
// Driver code
int main()
{
    // Declaring a max-heap priority
    // queue
    priority_queue<set<int> > priorityQueue;
 
    // Declaring a set of integers
    set<int> set1;
 
    // Inserting into the set
    set1.insert(10);
    set1.insert(1);
    set1.insert(2);
    set1.insert(5);
 
    // Push the set into priority
    // queue
    priorityQueue.push(set1);
 
    // Declaring another set
    set<int> set2;
 
    // Inserting into the set
    set2.insert(2);
    set2.insert(7);
    set2.insert(12);
    set2.insert(1);
 
    // Push the set into priority queue
    priorityQueue.push(set2);
 
    // Declaring another set
    set<int> set3;
 
    // Inserting into the set
    set3.insert(4);
    set3.insert(7);
    set3.insert(12);
    set3.insert(13);
 
    // Push the set into priority queue
    priorityQueue.push(set3);
 
    // Print the priority queue
    print(priorityQueue);
 
    return 0;
}
Producción

[ 4 7 12 13 ]
[ 1 2 7 12 ]
[ 1 2 5 10 ]

Por defecto, la cola de prioridad es un montón máximo, por lo tanto, internamente para dos conjuntos dentro de la cola de prioridad, el conjunto que tiene un primer elemento mayor es el elemento superior. Si el primer elemento es igual, se compara el segundo valor de los conjuntos y así sucesivamente.

Sintaxis:

priority_queue<set<data_type>, vector<set<data_type>>, greater<set<data_type>>> priorityQueue 
This stores set as an element in the min-heap priority queue

A continuación se muestra la implementación de la cola de prioridad min-heap de set:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print priority
// queue contents
void print(priority_queue<set<int>,
                          vector<set<int> >,
                          greater<set<int> > >
               priorityQueue)
{
    while (!priorityQueue.empty()) {
        // Each element of the priority
        // queue is a set itself
        set<int> st = priorityQueue.top();
 
        cout << "[ ";
 
        // Print the set elements
        for (auto element : st)
            cout << element << ' ';
 
        cout << ']';
        cout << '\n';
 
        // Pop out the topmost set
        priorityQueue.pop();
    }
}
 
// Driver code
int main()
{
    // Declaring a min-heap
    // priority queue
    priority_queue<set<int>,
                   vector<set<int> >,
                   greater<set<int> > >
        priorityQueue;
 
    // Declaring a set of integers
    set<int> set1;
 
    // Inserting into the set
    set1.insert(10);
    set1.insert(1);
    set1.insert(2);
    set1.insert(5);
 
    // Push the set into priority
    // queue
    priorityQueue.push(set1);
 
    // Declaring another set
    set<int> set2;
 
    // Inserting into the set
    set2.insert(2);
    set2.insert(7);
    set2.insert(12);
    set2.insert(1);
 
    // Push the set into priority
    // queue
    priorityQueue.push(set2);
 
    // Declaring another set
    set<int> set3;
 
    // Inserting into the set
    set3.insert(4);
    set3.insert(7);
    set3.insert(12);
    set3.insert(13);
 
    // Push the set into priority
    // queue
    priorityQueue.push(set3);
 
    // Print the priority queue
    print(priorityQueue);
 
    return 0;
}
Producción

[ 1 2 5 10 ]
[ 1 2 7 12 ]
[ 4 7 12 13 ]

Internamente, para dos conjuntos dentro de la cola de prioridad de almacenamiento dinámico mínimo, el conjunto que tiene el primer elemento más pequeño es el elemento superior. Si el primer elemento es igual, se compara el segundo valor de los conjuntos y así sucesivamente.

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 *