Priority Queue in Javascript
A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values.
We will store the elements of the Priority Queue in the heap structure. When using priority queues the highest priority element is always the root element.
Below is the implementation of the Priority Queue using Min Heap
class PriorityQueue {
constructor() {
this.heap = [];
}
// Helper Methods
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1;
}
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2;
}
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
hasLeftChild(index) {
return this.getLeftChildIndex(index) < this.heap.length;
}
hasRightChild(index) {
return this.getRightChildIndex(index) < this.heap.length;
}
hasParent(index) {
return this.getParentIndex(index) >= 0;
}
leftChild(index) {
return this.heap[this.getLeftChildIndex(index)];
}
rightChild(index) {
return this.heap[this.getRightChildIndex(index)];
}
parent(index) {
return this.heap[this.getParentIndex(index)];
}
swap(indexOne, indexTwo) {
const temp = this.heap[indexOne];
this.heap[indexOne] = this.heap[indexTwo];
this.heap[indexTwo] = temp;
}
peek() {
if (this.heap.length === 0) {
return null;
}
return this.heap[0];
}
// Removing an element will reomve the
// top element with highest priority then
// heapifyDown will be called
remove() {
if (this.heap.length === 0) {
return null;
}
const item = this.heap[0];
this.heap[0] = this.heap[this.heap.length - 1];
this.heap.pop();
this.heapifyDown();
return item;
}
add(item) {
this.heap.push(item);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
this.swap(this.getParentIndex(index), index);
index = this.getParentIndex(index);
}
}
heapifyDown() {
let index = 0;
while (this.hasLeftChild(index)) {
let smallerChildIndex = this.getLeftChildIndex(index);
if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
smallerChildIndex = this.getRightChildIndex(index);
}
if (this.heap[index] < this.heap[smallerChildIndex]) {
break;
} else {
this.swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
}
// Creating The Priority Queue
var PriQueue = new PriorityQueue();
// Adding the Elements
PriQueue.add(32);
PriQueue.add(45);
PriQueue.add(12);
PriQueue.add(65);
PriQueue.add(85);
console.log(PriQueue.peek());
console.log(PriQueue.remove());
console.log(PriQueue.peek());
console.log(PriQueue.remove());
console.log(PriQueue.peek());
console.log(PriQueue.remove());
Output
12 12 32 32 45 45
Below is the implementation of the Priority queue using Max Heap
class PriorityQueue {
constructor() {
this.heap = [];
}
// Helper Methods
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1;
}
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2;
}
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
hasLeftChild(index) {
return this.getLeftChildIndex(index) < this.heap.length;
}
hasRightChild(index) {
return this.getRightChildIndex(index) < this.heap.length;
}
hasParent(index) {
return this.getParentIndex(index) >= 0;
}
leftChild(index) {
return this.heap[this.getLeftChildIndex(index)];
}
rightChild(index) {
return this.heap[this.getRightChildIndex(index)];
}
parent(index) {
return this.heap[this.getParentIndex(index)];
}
swap(indexOne, indexTwo) {
const temp = this.heap[indexOne];
this.heap[indexOne] = this.heap[indexTwo];
this.heap[indexTwo] = temp;
}
peek() {
if (this.heap.length === 0) {
return null;
}
return this.heap[0];
}
// Removing an element will reomve the
// top element with highest priority then
// heapifyDown will be called
remove() {
if (this.heap.length === 0) {
return null;
}
const item = this.heap[0];
this.heap[0] = this.heap[this.heap.length - 1];
this.heap.pop();
this.heapifyDown();
return item;
}
add(item) {
this.heap.push(item);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
while (this.hasParent(index) && this.parent(index) < this.heap[index]) {
this.swap(this.getParentIndex(index), index);
index = this.getParentIndex(index);
}
}
heapifyDown() {
let index = 0;
while (this.hasLeftChild(index)) {
let smallerChildIndex = this.getLeftChildIndex(index);
if (this.hasRightChild(index) && this.rightChild(index) > this.leftChild(index)) {
smallerChildIndex = this.getRightChildIndex(index);
}
if (this.heap[index] > this.heap[smallerChildIndex]) {
break;
} else {
this.swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
}
// Creating The Priority Queue
var PriQueue = new PriorityQueue();
PriQueue.add(32);
PriQueue.add(45);
PriQueue.add(12);
PriQueue.add(65);
PriQueue.add(85);
// Removing and Checking elements of highest Priority
console.log(PriQueue.peek());
console.log(PriQueue.remove());
console.log(PriQueue.peek());
console.log(PriQueue.remove());
console.log(PriQueue.peek());
console.log(PriQueue.remove());
Output
85 85 65 65 45 45
Learn Data Structures with Javascript | DSA using JavaScript Tutorial
JavaScript (JS) is the most popular lightweight, interpreted compiled programming language, and might be your first preference for Client-side as well as Server-side developments. But have you thought about using Javascript for DSA? Learning Data Structures and Algorithms can be difficult when combined with Javascript. For this reason, we have brought to you this detailed DSA tutorial on how to get started with Data Structures with Javascript from scratch.
Table of Content
- What is Data Structure?
- How to start learning Data Structures with Javascript?
- Learn about Complexities
- Learn Data Structures with JavaScript
- Array in javascript
- String in javascript
- Linked List in Javascript
- Stack in Javascript
- Queue in Javascript
- Tree in Javascript
- Priority Queue in Javascript
- Map in Javascript
- Set in Javascript
- Graph in Javascript