Priority Queue in Javascript

Today, in this article we are going to learn about priority queues in javascript.

What is a priority queue?

In computer programming queue or general queue basically means the same thing. A queue is FIFO(First In First Out) which means if something goes first it will come out first.

In the priority queue, each task has its priority. A real-life example of a priority queue is patients in a hospital the ones with the most priority are treated first then the others.

Priority queues are used when making decisions among items with equal values but varying priorities or weights. They offer efficient retrieval of minimum values, making them well-suited for applications such as:

• Dijkstra's Shortest Path Algorithm: When the graph is represented as an adjacency list or matrix, priority queues can efficiently extract the minimum value during Dijkstra's algorithm execution.

• Prim's Algorithm: Priority queues are used to store node keys and extract the minimum key nodes at each step of Prim's algorithm.

• Data Compression: Priority queues are utilized in Huffman coding techniques for data compression.

• Operating Systems: Operating systems employ priority queues for load-balancing purposes.

There are different ways you can implement a priority queue in JavaScript. The most optimized way to create a priority queue in Javascript is to use a binary heap, specifically a min-heap, as it provides efficient O(log n) time complexity for both insertion and removal of elements. Javascript doesn't provide built-in binary heap data structure so for this post we are going to use diffferent approach. In later article we will learn to use binary heap as well.

List of operations performed on the Priority queue

• enqueue(): Adds an item at the tail of the queue

• dequeue(): Removes an item from the head of the queue

• front():

class QueueElement {
    constructor(element, priority) {
         this.element = element;
         this.priority = priority;
    }
}
class PriorityQueue {
    constructor() {
        this.items = [];
        this.enqueue = function (element, priority) {
            const queueElement = new QueueElement(element, priority);
            let added = false;

            for (let i = 0; i < this.items.length; i++) {
                if (queueElement.priority > this.items[i].priority) {
                    this.items.splice(i, 0, queueElement);
                    added = true;
                    break;
                }
            }

            if (!added) {
                this.items.push(queueElement);
            }
        };

        this.dequeue = () => {
            return this.items.shift();
        };

        this.front = () => {
            return this.items[0];
        };

        this.rear = () => {
            return this.items[this.items.length - 1];
        };

        this.isEmpty = () => {
            return this.items.length === 0;
        };

        this.size = () => {
            return this.items.length;
        };

        this.print = function () {
            for (let i = 0; i < this.items.length; i++) {
                console.log(`${this.items[i].element} - ${this.items[i].priority}`);
            }
        };
    }
}

// Example usage:

const priorityQueue = new PriorityQueue();
priorityQueue.enqueue("Task 1", 2);
priorityQueue.enqueue("Task 2", 1);
priorityQueue.enqueue("Task 3", 3);

console.log(priorityQueue.dequeue()); // Output: Object { element: "Task 2", priority: 1 }
console.log(priorityQueue.dequeue()); // Output: Object { element: "Task 1", priority: 2 }
console.log(priorityQueue.dequeue()); // Output: Object { element: "Task 3", priority: 3 }