How to implement Priority Queue In TypeScript

In a priority queue, each element has an associated priority. Elements with higher priorities are served before elements with lower priorities. In a priority queue, the element with the highest priority is served first.

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 our priority queue. Below are the list of patients which have name and priority.


    //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 }

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

Please do not post any spam link in the comment box😊

Post a Comment (0)
Previous Post Next Post