How to implement Priority Queue In TypeScript

A priority queue is a data structure where each element has an associated priority. Elements with higher priorities are served before elements with lower priorities. In JavaScript, you can implement a priority queue using an array. The array stores objects with “value” and “priority”

In JavaScript, you can implement a priority queue with an array. The array can store objects with a “value” and a “priority” properties.

To insert an element in the priority queue, you need to determine the correct position in the array that respects the priority order. The insertion of a new element in the priority queue can be done in O(n) time, with n being the number of elements in the array.

To extract the highest priority element, you need to remove the first element from the array. This operation can be done in O(1) time.

Priority queues can be implemented in JavaScript by using an array with two functions: one for adding new items and one for removing them.

Here is an example of how to implement a priority queue in JavaScript:

class PriorityQueue<T> {
    private _items: T[];
    private _comparator: (a: T, b: T) => number;
    
    constructor(comparator: (a: T, b: T) => number) {
        this._items = [];
        this._comparator = comparator;
    }
    
    public enqueue(item: T): void {
        this._items.push(item);
        this._items.sort(this._comparator);
    }
    
    public dequeue(): T |undefined{
        return this._items.shift();
    }
    
    public peek(): T {
        return this._items[0];
    }
    
    public get length(): number {
        return this._items.length;
    }
    }

How to Use

Let’s use the priority queue to manage a list of patients. Each patient has a name and a priority. We’ll enqueue the patients based on their priority and dequeue them to process in order.

    //list of patients
    const patients = [
    { name: 'John', priority: 2 },
    { name: 'Jack', priority: 1 },
    { name: 'Camila', priority: 1 },
    ];

Create a priority queue instance and pass the comparator function as a parameter. This is the most crucial component of our implementations. In this part, you can set the priority of the queue, which in our situation is the priority of the patients.

//comparator function
const comparator = (a: any, b: any) => {
  if (a.priority < b.priority) {
    return -1;
  }

  if (a.priority > b.priority) {
    return 1;
  }

  return 0;
};

//create a new priority queue
const priorityQueue = new PriorityQueue(comparator);

//add patients to the queue
patients.forEach((patient) => {
  priorityQueue.enqueue(patient);
});

//dequeue patients from the queue
while (priorityQueue.length > 0) {
  const patient = priorityQueue.dequeue();
  console.log(patient);
}

Output

{ name: 'Jack', priority: 1 } 
{ name: 'Camila', priority: 1 } 
{ name: 'John', priority: 2 }

Use Cases for a Priority Queue:

1. Task Scheduling: When dealing with a system that requires task scheduling, a priority queue can efficiently manage tasks based on their priorities. This could be useful in job scheduling, event management, or background processing scenarios.

2. Network Packet Routing: In network communication protocols, routing packets based on priorities is crucial to ensure efficient data transmission. A priority queue can help manage and process network packets based on their priorities, optimizing the overall network performance.

3. Event-driven Systems: In event-driven systems, such as event dispatchers or event queues, processing events based on their priorities is vital. A priority queue can handle event dispatching efficiently, ensuring critical events are handled promptly.

Conclusion

Implementing a priority queue in JavaScript empowers developers to manage and process elements based on their priorities effectively. With its versatile nature and customizable ordering, a priority queue is a valuable addition to any developer’s toolkit. By understanding the implementation details and exploring various use cases, you can leverage the power of a priority queue to enhance the efficiency and performance of your JavaScript applications. Start utilizing this powerful data structure today and unlock new possibilities in element processing.

THIS IS NOT OPTMIZIED IMPLEMENTIONS BETTER WAY TO IMPLEMENT PRIORITY QUEUE IS USING HEAP