# Data Structures: Priority Queue

## A simple guide to understanding Priority Queue π

Rehan Sattar
Β·Jul 24, 2021Β·

Subscribe to my newsletter and never miss my upcoming articles

## β¨ 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.

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! β¨