Data Structures: Priority Queue

Data Structures: Priority Queue

A simple guide to understanding Priority Queue πŸš€

✨ Introduction

In the previous part, we learned about queues. Now we will try to understand another useful variant of a queue i.e Priority Queue.

A priority queue is one where elements are added from the queue based on a priority constraint.

✨ Example

To understand priority queues, we can take the example of the Emergency Department (ED) of a hospital. When a patient enters the ED, he or she is seen by a triage nurse. This nurse’s job is to assess the severity of the patient’s condition and assign the patient a priority code. Patients with a high priority code are seen before patients with a lower priority code, and patients that have the same priority code are seen on a first-come, first-served, or first-in, first-out, basis.

Queue (2).jpg

Important: In this article, the highest number is the highest priority and the lowest number is the lowest priority. You can decide for yourself accordingly.

✨ Important Concept

  • In the priority queue, insertion is performed with respect the priority.

  • The delete operation depends on the sorting of the queue. If the queue is sorted with the highest priority at first, then delete will always be performed from one end. Otherwise, it also depends on the priority,

  • The time complexity is totally dependant on the operation and the algorithm. This means there is no guaranteed time complexity of a priority queue.

  • We keep track of priority manually in the priority queue.

πŸ‘‰ Let's check how to code a priority queue in JavaScript.

✨ Coding A Priority Queue In JavaScript

First, let's create a custom class for storing the element and the priority of a queue item.

class QueueItem {
  constructor(item, priority) {
    this.item = item; // The item of the queue, can be a string, number, boolean etc.
    this.priority = priority; // The priority of this particular item.
  }
}

Let's create a class for our Priority Queue. We are going to use Array to create a priority queue.

class PriorityQueue {
  constructor() {
    this.queue = []; // Initially, the queue is empty!
  }
}

✨ Operations

πŸ‘‰ enqueue

For enqueueing an item into the queue, we will follow these steps:

  1. Create a QueueItem.
  2. Iterate over the complete queue and find the best place with respect to the priority to insert the item.
  3. If the place is found, then break out from the loop for better performance.
  4. If the element has the highest priority, then we will add it to the front of the queue.
enqueue(item, priority) {
  // STEP 1:Create a `QueueItem`
  const queueItem = new QueueItem(item, priority);
  let inserted = false;

  // STEP 2: Iterate over the complete queue and find the best place with respect to the priority
  for (let i = 0; i < this.queue.length; i++) {
    if (this.queue[i].priority > queueItem.priority) {
      //  Insert the item.
      this.queue.splice(i, 0, queueItem);
      // STEP 3: If the place is found, then break out from the loop for better performance.
      inserted = true;
      break;
    }
  }

  // STEP 4: If the element has the highest priority, then we will add it to the front of queue.
  if (!inserted) {
    this.queue.push(qElement);
  }
}

πŸ‘‰ dequeue

For dequeue, we can remove the highest priority element.

dequeue() {
  return this.queue.pop();
}

πŸ‘‰ front

front returns the element which has the highest priority in priority queue.

front() {
  return this.queue[this.queue.length - 1];
}

πŸ‘‰ rear

rear returns the element which has the lowest priority in priority queue.

rear() {
  return this.queue[0];
}

πŸ‘‰ isEmpty

isEmpty is used to check if the queue is empty or not.

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

πŸ‘‰ size

size method is used to get the total length of the queue.

size() {
  return this.queue.length;
}

Let's test our Priority Queue.

const pq = new PriorityQueue();

pq.enqueue(1, 3);
pq.print();
/*
Item: 1, Priority: 3
*/

pq.enqueue(5, 2);
pq.print();
/*
Item: 1, Priority: 3
Item: 5, Priority: 2
*/

pq.enqueue(6, 1);
pq.print();
/*
Item: 1, Priority: 3
Item: 5, Priority: 2
Item: 6, Priority: 1
*/

pq.enqueue(11, 1);
pq.print();
/*
Item: 1, Priority: 3
Item: 5, Priority: 2
Item: 11, Priority: 1
Item: 6, Priority: 1
*/

pq.enqueue(13, 1);
pq.print();
/*
Item: 1, Priority: 3
Item: 5, Priority: 2
Item: 13, Priority: 1
Item: 11, Priority: 1
Item: 6, Priority: 1
*/

pq.enqueue(10, 3);
pq.print();
/*
Item: 10, Priority: 3
Item: 1, Priority: 3
Item: 5, Priority: 2
Item: 13, Priority: 1
Item: 11, Priority: 1
Item: 6, Priority: 1
*/

pq.dequeue();
pq.print();
/*
Item: 1, Priority: 3
Item: 5, Priority: 2
Item: 13, Priority: 1
Item: 11, Priority: 1
Item: 6, Priority: 1
*/

That's all folks!

That's it, folks! hope it was a good read for you. Thank you! ✨

πŸ‘‰ Follow me: Github Twitter LinkedIn Youtube

Β