# Data Structure: Priority Queue in JavaScript and TypeScript

Priority queues are very frequently used data structures. Used to generate a queue so that we can process the items based on the priority of it.

NOTE

In this article, we are discussing the implementation of Priority Queue in JavaScript and TypeScript.

Check the link below to check the details of Priority Queue-

Here we are using a Max Binary Heap to implement the Priority Queue. The code is mostly the same as Max Binary Heap, there are just a few differences-

## Priority Queue using Max Binary Heap

If we represent this Heap(binary tree) in an array, it will look like below-

Notice the indexes of the elements. Here can find the index of child elements from the index of parent, can find parent from the index of children, using the following formula-

• If the parent element is in N th index, then-
• Left child index: 2N + 1
• Right child index: 2N + 2
• If the child element is in N th index, then-
• Parent element index: floor((N – 1) / 2)

### Step #1: Node Class

Define class “Node”. This is used to store information of a single node.
Define fields – “data” and “priority”.
“data” field is used to store the actual data.
“priority” field is used to store the priority/importance of the node. In this case – the higher the priority value, the higher the importance is.
``````class Node {
constructor(data, priority) {
this.data = data;
this.priority = priority;
}
}``````

### Step #2: Priority Queue Class

Define class “PriorityQueue”.
Define property “nodes”. This is used to store the list of nodes in the priority queue.
Initialize the “nodes” field with an empty array, in the constructor.
``````class PriorityQueue {
constructor() {
this.nodes = [];
}
}``````

### Step #3: Enqueue Method

Define method “enqueue”.
Accept “data” and “priority” as parameters.
Create a node from the “data” and “priority”.
Push the node at the end of the array.
Check if the parent is smaller than the newly added element. If the parent is smaller, then swap the new node with the parent. Keep swapping until the new node reached the correct position.
``````class PriorityQueue {
// ...

// Insert item to the Heap
enqueue(data, priority) {
const newNode = new Node(data, priority);

// assume the item will be inserted
// at the end of the array initially
let itemIndex = this.nodes.length;

while (itemIndex > 0) {
// Get the index of parent of the new data
// Calculate by index
// If index of an element is N, the then parent index is Floor((N - 1) / 2)
const parentIndex = Math.floor((itemIndex - 1) / 2);

// if current item is smaller than then parent then we are good
// No changes required in that case
if (parentIndex < 0 || this.nodes[parentIndex].priority > newNode.priority) {
break;
}

this.nodes[itemIndex] = this.nodes[parentIndex];
itemIndex = parentIndex;
}

// finally push the item in the selected index
this.nodes[itemIndex] = newNode;

return itemIndex;
}

//...
}``````

### Step #4: Queue Position Setting Utility Method

Define method “setQueuePosition”. This method is used to move an item to the correct position based on the priority.

This function recursively calls itself until all the nodes reach the correct position.

``````class PriorityQueue {
// ...

// Utility function to bring an element
// to it's correct postion
setQueuePosition(currentIndex) {
let largestIndex = currentIndex;
let leftIndex = currentIndex * 2 + 1;
let rightIndex = currentIndex * 2 + 2;

if (
leftIndex < this.nodes.length &&
this.nodes[leftIndex].priority > this.nodes[largestIndex].priority
) {
largestIndex = leftIndex;
}

if (
rightIndex < this.nodes.length &&
this.nodes[rightIndex].priority > this.nodes[largestIndex].priority
) {
largestIndex = rightIndex;
}

// If either left or right node is larger than current node then swap
if (largestIndex !== currentIndex) {
const temp = this.nodes[currentIndex];
this.nodes[currentIndex] = this.nodes[largestIndex];
this.nodes[largestIndex] = temp;

// setQueuePosition the largest index element again
this.setQueuePosition(largestIndex);
}
}

// ...
}``````

### Step #5: Dequeue Method

Define method “dequeue”.
Return the current root, as this is the node with highest priority.
Then for the rest of the node, use the method “setQueuePosition” for putting the nodes to correct position.
``````class PriorityQueue {
// ...

// Extract the max item from the Heap
dequeue() {
// The max item is at the root
// So extract and store that in a const
const maxItem = this.nodes[0];

// Get the last element
const lastItem = this.nodes.pop();

// Implement setQueuePosition if there are items left
if (this.nodes.length > 0) {
// Set the last item as the root (temporary)
// The position is most probably not correct for this node
// we are setting this for now
// we will take it to the correct position in the next step
this.nodes[0] = lastItem;

// Bring the root element down if it is not the max item
this.setQueuePosition(0);
}

// Return the extracted node
return maxItem;
}

// ...
}``````

### Full Source Code

Here is the full source code of the Priority Queue implementation-

``````// pq.js
// Priority Queue implementation in JavaScript

class Node {
constructor(data, priority) {
this.data = data;
this.priority = priority;
}
}

class PriorityQueue {
constructor() {
this.nodes = [];
}

// Insert item to the Heap
enqueue(data, priority) {
const newNode = new Node(data, priority);

// assume the item will be inserted
// at the end of the array initially
let itemIndex = this.nodes.length;

while (itemIndex > 0) {
// Get the index of parent of the new data
// Calculate by index
// If index of an element is N, the then parent index is Floor((N - 1) / 2)
const parentIndex = Math.floor((itemIndex - 1) / 2);

// if current item is smaller than then parent then we are good
// No changes required in that case
if (parentIndex < 0 || this.nodes[parentIndex].priority > newNode.priority) {
break;
}

this.nodes[itemIndex] = this.nodes[parentIndex];
itemIndex = parentIndex;
}

// finally push the item in the selected index
this.nodes[itemIndex] = newNode;

return itemIndex;
}

// Extract the max item from the Heap
dequeue() {
// The max item is at the root
// So extract and store that in a const
const maxItem = this.nodes[0];

// Get the last element
const lastItem = this.nodes.pop();

// Implement setQueuePosition if there are items left
if (this.nodes.length > 0) {
// Set the last item as the root (temporary)
// The position is most probably not correct for this node
// we are setting this for now
// we will take it to the correct position in the next step
this.nodes[0] = lastItem;

// Bring the root element down if it is not the max item
this.setQueuePosition(0);
}

// Return the extracted node
return maxItem;
}

// Utility function to bring an element
// to it's correct postion
setQueuePosition(currentIndex) {
let largestIndex = currentIndex;
let leftIndex = currentIndex * 2 + 1;
let rightIndex = currentIndex * 2 + 2;

if (
leftIndex < this.nodes.length &&
this.nodes[leftIndex].priority > this.nodes[largestIndex].priority
) {
largestIndex = leftIndex;
}

if (
rightIndex < this.nodes.length &&
this.nodes[rightIndex].priority > this.nodes[largestIndex].priority
) {
largestIndex = rightIndex;
}

// If either left or right node is larger than current node then swap
if (largestIndex !== currentIndex) {
const temp = this.nodes[currentIndex];
this.nodes[currentIndex] = this.nodes[largestIndex];
this.nodes[largestIndex] = temp;

// setQueuePosition the largest index element again
this.setQueuePosition(largestIndex);
}
}
}

export default PriorityQueue;
``````

### Demo

Use the following code to check the implementation-

``````// demo.js
import PriorityQueue from "./pq.js";

// Create a new Priority Queue
let bigBoxPriorityQueue = new PriorityQueue();

console.log("n----------- Priority Queue - Enqueue example -----------n");

// Enqueue items
console.log("Enqueue - 100| Result Index: ", bigBoxPriorityQueue.enqueue('Shad Skiles', 100));
console.log("Enqueue - 150| Result Index: ", bigBoxPriorityQueue.enqueue('Isaias Hackett', 150));
console.log("Enqueue - 80| Result Index: ", bigBoxPriorityQueue.enqueue('Reggie Blick', 80));
console.log("Enqueue - 110| Result Index: ", bigBoxPriorityQueue.enqueue('Kali Feil', 110));
console.log("Enqueue - 40| Result Index: ", bigBoxPriorityQueue.enqueue('Jadyn Lesch', 40));
console.log("Enqueue - 120| Result Index: ", bigBoxPriorityQueue.enqueue('Candice Braun', 120));
console.log("Enqueue - 10| Result Index: ", bigBoxPriorityQueue.enqueue('Bailey Keeling', 10));
console.log("Enqueue - 190| Result Index: ", bigBoxPriorityQueue.enqueue('Jamil Bartoletti', 190));
console.log("Enqueue - 55| Result Index: ", bigBoxPriorityQueue.enqueue('Laurie Rowe', 55));
console.log("Enqueue - 60| Result Index: ", bigBoxPriorityQueue.enqueue('Jed Emard', 60));

console.log(
"nn----------- Priority Queue - Dequeue example -----------n"
);

for (let i = 0; i < 12; i++) {
console.log("Dequeue | Result: ", bigBoxPriorityQueue.dequeue());
}
``````

Output:

Here is the output of the demo code-

``````----------- Priority Queue - Enqueue example -----------

Enqueue - 100| Result Index:  0
Enqueue - 150| Result Index:  0
Enqueue - 80| Result Index:  2
Enqueue - 110| Result Index:  1
Enqueue - 40| Result Index:  4
Enqueue - 120| Result Index:  2
Enqueue - 10| Result Index:  6
Enqueue - 190| Result Index:  0
Enqueue - 55| Result Index:  8
Enqueue - 60| Result Index:  4

----------- Priority Queue - Dequeue example -----------

Dequeue | Result:  Node { data: 'Jamil Bartoletti', priority: 190 }
Dequeue | Result:  Node { data: 'Isaias Hackett', priority: 150 }
Dequeue | Result:  Node { data: 'Candice Braun', priority: 120 }
Dequeue | Result:  Node { data: 'Kali Feil', priority: 110 }
Dequeue | Result:  Node { data: 'Shad Skiles', priority: 100 }
Dequeue | Result:  Node { data: 'Reggie Blick', priority: 80 }
Dequeue | Result:  Node { data: 'Jed Emard', priority: 60 }
Dequeue | Result:  Node { data: 'Laurie Rowe', priority: 55 }
Dequeue | Result:  Node { data: 'Jadyn Lesch', priority: 40 }
Dequeue | Result:  Node { data: 'Bailey Keeling', priority: 10 }
Dequeue | Result:  undefined
Dequeue | Result:  undefined``````

### Testing

Here are the tests for the Priority Queue implementation-

``````// pq.test.js
import { describe, it, beforeEach, expect } from "vitest";
import PriorityQueue from "./pq";

describe("Priority Queue", () => {
let priorityQueue;

beforeEach(() => {
priorityQueue = new PriorityQueue();
priorityQueue.enqueue("Isaias Hackett", 150);
priorityQueue.enqueue("Reggie Blick", 80);
priorityQueue.enqueue("Kali Feil", 110);
priorityQueue.enqueue("Candice Braun", 120);
priorityQueue.enqueue("Bailey Keeling", 10);
priorityQueue.enqueue("Jamil Bartoletti", 190);
priorityQueue.enqueue("Laurie Rowe", 55);
priorityQueue.enqueue("Jed Emard", 60);
});

describe("Enqueue item to Priority Queue", () => {
it("Should have correct length", () => {
expect(priorityQueue.nodes.length).toBe(10);
});

it("Should have correct sequence of items", () => {
expect(priorityQueue.nodes.map(node => node.priority)).toMatchObject([
190, 150, 120, 110, 60, 80, 10, 100, 55, 40,
]);
});
});

describe("Dequeue items from Priority Queue", () => {
it("Should dequeue correct item", () => {
expect(priorityQueue.dequeue().priority).toBe(190);
expect(priorityQueue.dequeue().priority).toBe(150);
expect(priorityQueue.dequeue().priority).toBe(120);
expect(priorityQueue.dequeue().priority).toBe(110);
expect(priorityQueue.dequeue().priority).toBe(100);
expect(priorityQueue.dequeue().priority).toBe(80);
expect(priorityQueue.dequeue().priority).toBe(60);
expect(priorityQueue.dequeue().priority).toBe(55);
expect(priorityQueue.dequeue().priority).toBe(40);
expect(priorityQueue.dequeue().priority).toBe(10);
expect(priorityQueue.dequeue()).toBeUndefined();
});
});
});
``````