¿Qué es la cola de prioridad? Introducción a la cola de prioridad

Priority Queue es un tipo de datos abstracto que es similar a una cola , y cada elemento tiene algún valor de prioridad asociado. La prioridad de los elementos en una cola de prioridad determina el orden en que se sirven los elementos (es decir, el orden en que se eliminan). Si en algún caso los elementos tienen la misma prioridad, se sirven según su orden en la cola.

Por lo tanto, todos los elementos están dispuestos en orden ascendente o descendente.

Propiedades de la cola de prioridad

Entonces, una cola de prioridad es una extensión de la cola con las siguientes propiedades. 

• Cada elemento tiene una prioridad asociada.
• Un elemento con prioridad alta se elimina de la cola antes que un elemento con prioridad baja.
• Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.

En la cola de prioridad a continuación, un elemento con un valor ASCII máximo tendrá la prioridad más alta. Los elementos con mayor prioridad se sirven primero. 

¿Cómo se asigna la Prioridad a los elementos en una Cola de Prioridad?

En una cola de prioridad, generalmente, se considera el valor de un elemento para asignar la prioridad. 

Por ejemplo, al elemento con el valor más alto se le asigna la prioridad más alta y al elemento con el valor más bajo se le asigna la prioridad más baja. También se puede utilizar el caso inverso, es decir, al elemento con el valor más bajo se le puede asignar la prioridad más alta. Además, la prioridad se puede asignar de acuerdo a nuestras necesidades. 

Operaciones de una cola de prioridad:

Una cola de prioridad típica admite las siguientes operaciones:

1) Inserción en una cola de prioridad

Cuando se inserta un nuevo elemento en una cola de prioridad, se mueve al espacio vacío de arriba a abajo y de izquierda a derecha. Sin embargo, si el elemento no está en el lugar correcto, se comparará con el Node principal. Si el elemento no está en el orden correcto, los elementos se intercambian. El proceso de intercambio continúa hasta que todos los elementos se colocan en la posición correcta.

2) Eliminación en una cola de prioridad  

Como sabe, en un montón máximo, el elemento máximo es el Node raíz. Y eliminará primero el elemento que tiene máxima prioridad. Por lo tanto, elimina el Node raíz de la cola. Esta eliminación crea una ranura vacía, que se llenará aún más con una nueva inserción. Luego, compara el elemento recién insertado con todos los elementos dentro de la cola para mantener el montón invariable.

3) Mirar en una cola de prioridad

Esta operación ayuda a devolver el elemento máximo de Max Heap o el elemento mínimo de Min Heap sin eliminar el Node de la cola de prioridad.

Tipos de cola de prioridad:

1) Cola de prioridad de orden ascendente

Como sugiere el nombre, en la cola de prioridad en orden ascendente, el elemento con un valor de prioridad más bajo recibe una prioridad más alta en la lista de prioridad. Por ejemplo, si tenemos los siguientes elementos en una cola de prioridad dispuestos en orden ascendente como 4,6,8,9,10. Aquí, 4 es el número más pequeño, por lo tanto, obtendrá la prioridad más alta en una cola de prioridad.

2) Cola de prioridad en orden descendente 

El Node raíz es el elemento máximo en un montón máximo, como sabrá. También eliminará primero el elemento con la prioridad más alta. Como resultado, el Node raíz se elimina de la cola. Esta eliminación deja un espacio vacío, que se llenará con nuevas inserciones en el futuro. El montón invariante se mantiene luego comparando el elemento recién insertado con todas las demás entradas en la cola.

Tipos de colas de prioridad

¿Diferencia entre la cola de prioridad y la cola normal?

No hay prioridad asociada a los elementos en una cola, se implementa la regla de primero en entrar, primero en salir (FIFO), mientras que, en una cola de prioridad, los elementos tienen una prioridad. Los elementos con mayor prioridad se sirven primero.

¿Cómo implementar la cola de prioridad? 

La cola de prioridad se puede implementar utilizando las siguientes estructuras de datos: 

• arreglos
• Lista enlazada
• Estructura de datos del montón
• Árbol de búsqueda binario

Vamos a discutir todo esto en detalle.

1) Implementar cola de prioridad usando array: 

Una implementación simple es usar una array con la siguiente estructura. 

elemento de estructura {
        int elemento;
        prioridad int;
}

• enqueue(): esta función se utiliza para insertar nuevos datos en la cola.
• dequeue(): esta función elimina el elemento con la prioridad más alta de la cola.
• peek()/top(): esta función se usa para obtener el elemento de mayor prioridad en la cola sin eliminarlo de la cola.

// C++ program to implement Priority Queue
// using Arrays
#include <bits/stdc++.h>
using namespace std;
 
// Structure for the elements in the
// priority queue
struct item {
    int value;
    int priority;
};
 
// Store the element of a priority queue
item pr[100000];
 
// Pointer to the last index
int size = -1;
 
// Function to insert a new element
// into priority queue
void enqueue(int value, int priority)
{
    // Increase the size
    size++;
 
    // Insert the element
    pr[size].value = value;
    pr[size].priority = priority;
}
 
// Function to check the top element
int peek()
{
    int highestPriority = INT_MIN;
    int ind = -1;
 
    // Check for the element with
    // highest priority
    for (int i = 0; i <= size; i++) {
 
        // If priority is same choose
        // the element with the
        // highest value
        if (highestPriority == pr[i].priority && ind > -1
            && pr[ind].value < pr[i].value) {
            highestPriority = pr[i].priority;
            ind = i;
        }
        else if (highestPriority < pr[i].priority) {
            highestPriority = pr[i].priority;
            ind = i;
        }
    }
 
    // Return position of the element
    return ind;
}
 
// Function to remove the element with
// the highest priority
void dequeue()
{
    // Find the position of the element
    // with highest priority
    int ind = peek();
 
    // Shift the element one index before
    // from the position of the element
    // with highest priority is found
    for (int i = ind; i < size; i++) {
        pr[i] = pr[i + 1];
    }
 
    // Decrease the size of the
    // priority queue by one
    size--;
}
 
// Driver Code
int main()
{
    // Function Call to insert elements
    // as per the priority
    enqueue(10, 2);
    enqueue(14, 4);
    enqueue(16, 4);
    enqueue(12, 3);
 
    // Stores the top element
    // at the moment
    int ind = peek();
 
    cout << pr[ind].value << endl;
 
    // Dequeue the top element
    dequeue();
 
    // Check the top element
    ind = peek();
    cout << pr[ind].value << endl;
 
    // Dequeue the top element
    dequeue();
 
    // Check the top element
    ind = peek();
    cout << pr[ind].value << endl;
 
    return 0;
}

// Java program to implement Priority Queue
// using Arrays
import java.util.*;
 
// Structure for the elements in the
// priority queue
class item {
  public int value;
  public int priority;
};
 
class GFG {
 
  // Store the element of a priority queue
  static item[] pr = new item[100000];
 
  // Pointer to the last index
  static int size = -1;
  // Function to insert a new element
  // into priority queue
  static void enqueue(int value, int priority)
  {
    // Increase the size
    size++;
 
    // Insert the element
    pr[size] = new item();
    pr[size].value = value;
    pr[size].priority = priority;
  }
 
  // Function to check the top element
  static int peek()
  {
    int highestPriority = Integer.MIN_VALUE;
    int ind = -1;
 
    // Check for the element with
    // highest priority
    for (int i = 0; i <= size; i++) {
 
      // If priority is same choose
      // the element with the
      // highest value
      if (highestPriority == pr[i].priority
          && ind > -1
          && pr[ind].value < pr[i].value) {
        highestPriority = pr[i].priority;
        ind = i;
      }
      else if (highestPriority < pr[i].priority) {
        highestPriority = pr[i].priority;
        ind = i;
      }
    }
 
    // Return position of the element
    return ind;
  }
 
  // Function to remove the element with
  // the highest priority
  static void dequeue()
  {
    // Find the position of the element
    // with highest priority
    int ind = peek();
 
    // Shift the element one index before
    // from the position of the element
    // with highest priority is found
    for (int i = ind; i < size; i++) {
      pr[i] = pr[i + 1];
    }
 
    // Decrease the size of the
    // priority queue by one
    size--;
  }
 
  public static void main(String[] args)
  {
    // Function Call to insert elements
    // as per the priority
    enqueue(10, 2);
    enqueue(14, 4);
    enqueue(16, 4);
    enqueue(12, 3);
 
    // Stores the top element
    // at the moment
    int ind = peek();
 
    System.out.println(pr[ind].value);
 
    // Dequeue the top element
    dequeue();
 
    // Check the top element
    ind = peek();
    System.out.println(pr[ind].value);
 
    // Dequeue the top element
    dequeue();
 
    // Check the top element
    ind = peek();
    System.out.println(pr[ind].value);
  }
}
 
// this code is contributed by phasing17

// C# program to implement Priority Queue
// using Arrays
 
using System;
 
// Structure for the elements in the
// priority queue
public class item {
    public int value;
    public int priority;
};
 
 
public class GFG
{
     
    // Store the element of a priority queue
    static item[] pr = new item[100000];
 
    // Pointer to the last index
    static int size = -1;
    // Function to insert a new element
    // into priority queue
    static void enqueue(int value, int priority)
    {
        // Increase the size
        size++;
     
        // Insert the element
        pr[size] = new item();
        pr[size].value = value;
        pr[size].priority = priority;
    }
     
    // Function to check the top element
    static int peek()
    {
        int highestPriority =  int.MinValue;
        int ind = -1;
     
        // Check for the element with
        // highest priority
        for (int i = 0; i <= size; i++) {
     
            // If priority is same choose
            // the element with the
            // highest value
            if (highestPriority == pr[i].priority && ind > -1
                && pr[ind].value < pr[i].value) {
                highestPriority = pr[i].priority;
                ind = i;
            }
            else if (highestPriority < pr[i].priority) {
                highestPriority = pr[i].priority;
                ind = i;
            }
        }
     
        // Return position of the element
        return ind;
    }
     
    // Function to remove the element with
    // the highest priority
    static void dequeue()
    {
        // Find the position of the element
        // with highest priority
        int ind = peek();
     
        // Shift the element one index before
        // from the position of the element
        // with highest priority is found
        for (int i = ind; i < size; i++) {
            pr[i] = pr[i + 1];
        }
     
        // Decrease the size of the
        // priority queue by one
        size--;
    }
 
    public static void Main(string[] args)
    {
         // Function Call to insert elements
        // as per the priority
        enqueue(10, 2);
        enqueue(14, 4);
        enqueue(16, 4);
        enqueue(12, 3);
     
        // Stores the top element
        // at the moment
        int ind = peek();
     
        Console.WriteLine(pr[ind].value);
     
        // Dequeue the top element
        dequeue();
     
        // Check the top element
        ind = peek();
        Console.WriteLine(pr[ind].value);
     
        // Dequeue the top element
        dequeue();
     
        // Check the top element
        ind = peek();
        Console.WriteLine(pr[ind].value);
    }
}
 
//this code is contributed by phasing17

// JavaScript program to implement Priority Queue
// using Arrays
 
// Structure for the elements in the
// priority queue
class item {
    constructor()
    {
        this.value;
        this.priority;
    }
};
 
// Store the element of a priority queue
let pr = [];
for (var i = 0; i < 100000; i++)
    pr.push(new item());
 
// Pointer to the last index
let size = -1;
 
// Function to insert a new element
// into priority queue
function enqueue(value, priority)
{
    // Increase the size
    size++;
 
    // Insert the element
    pr[size] = new item();
    pr[size].value = value;
    pr[size].priority = priority;
}
 
// Function to check the top element
function peek()
{
    let highestPriority = Number.MIN_SAFE_INTEGER;
    let ind = -1;
 
    // Check for the element with
    // highest priority
    for (var i = 0; i <= size; i++) {
 
        // If priority is same choose
        // the element with the
        // highest value
        if (highestPriority == pr[i].priority && ind > -1
            && pr[ind].value < pr[i].value) {
            highestPriority = pr[i].priority;
            ind = i;
        }
        else if (highestPriority < pr[i].priority) {
            highestPriority = pr[i].priority;
            ind = i;
        }
    }
 
    // Return position of the element
    return ind;
}
 
// Function to remove the element with
// the highest priority
function dequeue()
{
    // Find the position of the element
    // with highest priority
    let ind = peek();
 
    // Shift the element one index before
    // from the position of the element
    // with highest priority is found
    for (var i = ind; i < size; i++) {
        pr[i] = pr[i + 1];
    }
 
    // Decrease the size of the
    // priority queue by one
    size--;
}
 
// Function Call to insert elements
// as per the priority
enqueue(10, 2);
enqueue(14, 4);
enqueue(16, 4);
enqueue(12, 3);
 
// Stores the top element
// at the moment
let ind = peek();
 
console.log(pr[ind].value);
 
// Dequeue the top element
dequeue();
 
// Check the top element
ind = peek();
console.log(pr[ind].value);
 
// Dequeue the top element
dequeue();
 
// Check the top element
ind = peek();
console.log(pr[ind].value);
 
// this code is contributed by phasing17

16
14
12

Nota: Lea este artículo para obtener más detalles.

2) Implementar la cola de prioridad usando la lista enlazada: 

En una implementación de LinkedList, las entradas se clasifican en orden descendente según su prioridad. El elemento de mayor prioridad siempre se agrega al frente de la cola de prioridad, que se forma mediante listas enlazadas. Las funciones como push() , pop() y peek() se usan para implementar una cola de prioridad usando una lista enlazada y se explican a continuación:

• push(): esta función se utiliza para insertar nuevos datos en la cola.
• pop(): esta función elimina el elemento con la prioridad más alta de la cola.
• peek() / top(): esta función se usa para obtener el elemento de mayor prioridad en la cola sin eliminarlo de la cola.

// C++ code to implement Priority Queue
// using Linked List
#include <bits/stdc++.h>
using namespace std;
 
// Node
typedef struct node {
    int data;
 
    // Lower values indicate
    // higher priority
    int priority;
 
    struct node* next;
 
} Node;
 
// Function to create a new node
Node* newNode(int d, int p)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = d;
    temp->priority = p;
    temp->next = NULL;
 
    return temp;
}
 
// Return the value at head
int peek(Node** head) { return (*head)->data; }
 
// Removes the element with the
// highest priority form the list
void pop(Node** head)
{
    Node* temp = *head;
    (*head) = (*head)->next;
    free(temp);
}
 
// Function to push according to priority
void push(Node** head, int d, int p)
{
    Node* start = (*head);
 
    // Create new Node
    Node* temp = newNode(d, p);
 
    // Special Case: The head of list has
    // lesser priority than new node
    if ((*head)->priority < p) {
 
        // Insert New Node before head
        temp->next = *head;
        (*head) = temp;
    }
    else {
 
        // Traverse the list and find a
        // position to insert new node
        while (start->next != NULL
               && start->next->priority > p) {
            start = start->next;
        }
 
        // Either at the ends of the list
        // or at required position
        temp->next = start->next;
        start->next = temp;
    }
}
 
// Function to check is list is empty
int isEmpty(Node** head) { return (*head) == NULL; }
 
// Driver code
int main()
{
 
    // Create a Priority Queue
    // 7->4->5->6
    Node* pq = newNode(4, 1);
    push(&pq, 5, 2);
    push(&pq, 6, 3);
    push(&pq, 7, 0);
 
    while (!isEmpty(&pq)) {
        cout << " " << peek(&pq);
        pop(&pq);
    }
    return 0;
}

 6 5 4 7

Consulte este artículo para obtener más detalles.

Nota: También podemos usar la lista enlazada, la complejidad temporal de todas las operaciones con la lista enlazada sigue siendo la misma que la array. La ventaja con la lista enlazada es eliminar la prioridad más alta() puede ser más eficiente ya que no tenemos que mover elementos. 

3) Implementar la cola de prioridad usando montones: 

Binary Heap generalmente se prefiere para la implementación de la cola de prioridad porque los montones proporcionan un mejor rendimiento en comparación con las arrays o LinkedList. Las operaciones en Binary Heap son las siguientes: 

• insert(p): Inserta un nuevo elemento con prioridad p.
• extractMax(): Extrae un elemento con máxima prioridad.
• remove(i): Elimina un elemento apuntado por un iterador i.
• getMax(): Devuelve un elemento con máxima prioridad.
• changePriority(i, p): Cambia la prioridad de un elemento apuntado por i a p .

Consulte este artículo para la implementación del código. 

4) Implementar la cola de prioridad usando el árbol de búsqueda binaria: 

También se puede utilizar un árbol de búsqueda binario autoequilibrado como el árbol AVL, el árbol rojo-negro, etc. para implementar una cola de prioridad. Las operaciones como peek(), insert() y delete() se pueden realizar usando BST.

Aplicaciones de Priority Queue: 

• Programación de CPU
• Graficar algoritmos como el algoritmo de ruta más corta de Dijkstra , el árbol de expansión mínimo de Prim , etc.
• Implementación de pila
• Todas las aplicaciones en cola donde la prioridad está involucrada.
• Compresión de datos en código Huffman
• Simulación basada en eventos, como clientes que esperan en una cola.
• Encontrar el K-ésimo elemento más grande/más pequeño.

Ver también: 

1. Aplicaciones de Priority Queue
2. Cola de prioridad en C++
3. Cola de prioridad en Java
4. Cola de prioridad en Python
5. Cola de prioridad en JavaScript
6. Artículos recientes sobre Priority Queue!