Implementación de Priority Queue en Javascript

Priority Queue es una extensión de Queue que tiene algunas de las siguientes propiedades: 

1. Cada elemento de la cola de prioridad tiene una prioridad asociada.
2. Los elementos se agregan a la cola según la prioridad.
3. Los elementos de menor prioridad se eliminan primero.

Podemos diseñar una cola de prioridad usando dos enfoques en el primer caso, podemos agregar el elemento de la cola al final de la cola y podemos eliminar los elementos de la cola dependiendo de la prioridad. En el segundo caso, podemos agregar elementos a la cola según la prioridad y eliminarlos del frente de la cola. En este artículo, usaríamos el segundo enfoque para implementar una cola de prioridad. 

Nota: Suponiendo que una cola de prioridad pueda crecer dinámicamente, no estamos considerando la condición de desbordamiento. 

Veamos un ejemplo de una clase de cola de prioridad: 

Ejemplo:  

// User defined class
// to store element and its priority
class QElement {
    constructor(element, priority)
    {
        this.element = element;
        this.priority = priority;
    }
}
 
// PriorityQueue class
class PriorityQueue {
 
    // An array is used to implement priority
    constructor()
    {
        this.items = [];
    }
 
    // functions to be implemented
    // enqueue(item, priority)
    // dequeue()
    // front()
    // isEmpty()
    // printPQueue()
}

Como puede ver en el ejemplo anterior, hemos definido el esqueleto de la clase PriorityQueue . Hemos utilizado una clase QElement definida por el usuario que tiene dos elementos de propiedad y prioridad. Hemos usado una array en la clase PriorityQueue para implementar la cola de prioridad, esta array es un contenedor de QElement. 

1. enqueue() : añade un elemento a la cola según su prioridad. 

// enqueue function to add element
// to the queue as per priority
enqueue(element, priority)
{
    // creating object from queue element
    var qElement = new QElement(element, priority);
    var contain = false;
 
    // iterating through the entire
    // item array to add element at the
    // correct location of the Queue
    for (var i = 0; i < this.items.length; i++) {
        if (this.items[i].priority > qElement.priority) {
            // Once the correct location is found it is
            // enqueued
            this.items.splice(i, 0, qElement);
            contain = true;
            break;
        }
    }
 
    // if the element have the highest priority
    // it is added at the end of the queue
    if (!contain) {
        this.items.push(qElement);
    }
}

En este método, creamos un qElement con elemento de propiedad y prioridad . Luego iteramos sobre la cola para encontrar la ubicación correcta del qElement según su prioridad y lo agregamos.

2. dequeue() : elimina un elemento de la cola de prioridad 

// dequeue method to remove
// element from the queue
dequeue()
{
    // return the dequeued element
    // and remove it.
    // if the queue is empty
    // returns Underflow
    if (this.isEmpty())
        return "Underflow";
    return this.items.shift();
}

Esta función elimina un elemento del principio de una cola ya que el elemento de mayor prioridad se almacena al principio de la cola de prioridad. Hemos utilizado el método de cambio de una array para eliminar un elemento de la cola.

3. front() : devuelve el elemento frontal de la cola de prioridad 

// front function
front()
{
    // returns the highest priority element
    // in the Priority queue without removing it.
    if (this.isEmpty())
        return "No elements in Queue";
    return this.items[0];
}

Esta función devuelve el elemento frontal de la cola de prioridad. Simplemente devolvemos el elemento 0 de una array para obtener el frente de una cola de prioridad.

4. rear() : devuelve el último elemento de la cola de prioridad 

// rear function
rear()
{
    // returns the lowest priority
    // element of the queue
    if (this.isEmpty())
        return "No elements in Queue";
    return this.items[this.items.length - 1];
}

Esta función devuelve el último elemento de la cola o el elemento de menor prioridad.

Métodos auxiliares: 
Declaremos algún método auxiliar que sea bastante útil al trabajar con la cola de prioridad.  

1. isEmpty() : devuelve verdadero si la cola de prioridad está vacía

// isEmpty function
isEmpty()
{
    // return true if the queue is empty.
    return this.items.length == 0;
}

Hemos utilizado la propiedad de longitud de una array para obtener la longitud y si es 0, la cola de prioridad está vacía. 
 

2. printPQueue() : imprime el elemento de la cola según la prioridad, comenzando de mayor a menor 
 

// printQueue function
// prints all the element of the queue
printPQueue()
{
    var str = "";
    for (var i = 0; i < this.items.length; i++)
        str += this.items[i].element + " ";
    return str;
}

En este método, concatenamos la propiedad del elemento de cada elemento de la cola de prioridad en una string.

Nota: – Aquí consideramos «1» como el elemento de mayor prioridad, puede modificar esto según el requisito. 

Implementación 
ahora Vamos a usar esta clase de cola de prioridad y su método diferente descrito anteriormente 

// creating object for queue class
var priorityQueue = new PriorityQueue();
 
// testing isEmpty and front on an empty queue
// return true
console.log(priorityQueue.isEmpty());
 
// returns "No elements in Queue"
console.log(priorityQueue.front());
 
// adding elements to the queue
priorityQueue.enqueue("Sumit", 2);
priorityQueue.enqueue("Gourav", 1);
priorityQueue.enqueue("Piyush", 1);
priorityQueue.enqueue("Sunny", 2);
priorityQueue.enqueue("Sheru", 3);
 
// prints [Gourav Piyush Sumit Sunny Sheru]
console.log(priorityQueue.printPQueue());
 
// prints Gourav
console.log(priorityQueue.front().element);
 
// prints Sheru
console.log(priorityQueue.rear().element);
 
// removes Gouurav
// priorityQueue contains
// [Piyush Sumit Sunny Sheru]
console.log(priorityQueue.dequeue().element);
 
// Adding another element to the queue
priorityQueue.enqueue("Sunil", 2);
 
// prints [Piyush Sumit Sunny Sunil Sheru]
console.log(priorityQueue.printPQueue());

Este artículo es una contribución de Sumit Ghosh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.