In this tutorial, we will explore the priority queue data structure in JavaScript. Essentially, a priority queue is a type of data structure that resembles both a queue and a stack. The distinguishing factor is that each element is assigned a "priority." In a priority queue, elements with higher priorities are processed before those with lower priorities. When two items have identical priorities, they are organized based on their order of appearance within the queue.
A Priority Queue is one of the special types of Queues that have the following specific features:
- Every element in the priority queue has a specific priority.
- Elements are enqueued based on their priority levels.
- The least priority elements are dequeued first.
A priority queue can be implemented in two primary manners. The first method involves adding elements to the end of the queue during the enqueue operation and subsequently removing them according to their priority during the dequeue operation. The second method entails inserting elements into the queue according to their priority and removing them from the front. This article will concentrate on implementing a priority queue using the latter technique.
Note: Assuming a priority queue can grow dynamically we are not considering the overflow condition.
The default JavaScript library does not feature a built-in priority queue. Nonetheless, you can create a priority queue utilizing different data structures, with one of the most frequently employed choices being a binary heap.
Binary Heap
A binary heap is a uniquely structured data organization that enables elements within an array to be sorted according to their priority levels. It resembles an array where the values are organized in either ascending or descending order based on a specified key. Elements with the highest (or lowest) priority are positioned nearer to the beginning of the array. This configuration facilitates the efficient retrieval and removal of an element that signifies the highest priority (or the minimum value).
Types
Min Heap: A min heap is organized in such a way that an element with a lower priority, or the minimum value, is positioned at the topmost part of the heap, known as the root. This structure allows for direct access to the minimum element in the queue, and the configuration of the min heap guarantees that each parent node's value is less than that of its child nodes.
Max Heap: A max heap is characterized as a heap in which the topmost element holds the highest priority, or the maximum value. This arrangement enables straightforward access to the maximum element during the dequeuing process. The configuration of a max heap ensures that every parent node possesses a value that exceeds that of its child nodes, thereby establishing a structure that supports rapid retrieval of the maximum element. The max heap structure confirms that each parent node is greater than its child nodes, resulting in a hierarchical organization that allows for effortless identification of the maximum element.
Implementation
Enqueue: This refers to the operation of adding an item to the queue.
Syntax:
// enqueue function to add an element
// to the queue as per priority
enqueue(element, priority)
{
// creating object from queue element
let qElement = new QElement(element, priority);
let contain = false;
// iterating through the entire
// item array to add element at the
// correct location of the Queue
for (let i = 0; i < this.items.length; i++) {
if (this.items[i].priority > qElement.priority) {
// Once the correct location is found it is
// enqueued
this.items.splice(i, 0, qElement);
contain = true;
break;
}
}
// if the element have the highest priority
// it is added at the end of the queue
if (!contain) {
this.items.push(qElement);
}
}
In this approach, we establish a qElement that contains an element attribute along with a priority characteristic. We then navigate through the queue to determine the precise location where the qElement, which possesses either the highest or lowest priority or the lowest among those with the highest priorities, should be inserted.
Dequeue: The operation of removing an element from the queue.
Syntax:
// dequeue method to remove
// element from the queue
dequeue()
{
// return the dequeued element
// and remove it.
// if the queue is empty
// returns Underflow
if (this.isEmpty())
return "Underflow";
return this.items.shift();
}
This operation eliminates an element from the front of a queue, as the highest priority element must reside at the front of a priority queue. In this context, the array's shift method is employed to remove the element from the queue.
Min Heap Implementation
Enqueue: The process of adding an element to the queue in alignment with the least priority.
Dequeue: Removing an element from the queue, beginning with the frontmost item.
class PriorityQueue{
constructor(){
this.values = [];
}
enqueue(node, priority){
var flag = false;
for(let i=0; i<this.values.length; i++){
if(this.values[i].priority>priority){
this.values.splice(i, 0, {node, priority})
flag = true;
break;
}
}
if(!flag){
this.values.push({node, priority})
}
}
dequeue(){
return this.values.shift()
}
size(){
return this.values.length;
}
}
var a = new PriorityQueue()
a.enqueue(2,10)
a.enqueue(4, 3)
a.enqueue(5,1)
console.log(a.dequeue())
console.log(a.dequeue())
console.log(a.dequeue())
Output
Max Heap Implementation
Enqueue: The process of adding an element to the queue based on its highest priority.
Dequeue: Removing an element from the front of the queue.
class PriorityQueue{
constructor(){
this.values = [];
}
enqueue(node, priority){
var flag = false;
for(let i=0; i<this.values.length; i++){
if(this.values[i].priority<priority){
this.values.splice(i, 0, {node, priority})
flag = true;
break;
}
}
if(!flag){
this.values.push({node, priority})
}
}
dequeue(){
return this.values.shift()
}
size(){
return this.values.length;
}
}
var a = new PriorityQueue()
a.enqueue(3,5)
a.enqueue(7, 4)
a.enqueue(5,0)
console.log(a.dequeue())
console.log(a.dequeue())
console.log(a.dequeue())
Output
Conclusion
JavaScript does not include a built-in priority queue; nevertheless, this essential implementation proves beneficial for operations that necessitate efficient prioritization. It can be adapted to operate as a min heap or a max heap, based on particular needs, showcasing the versatility of JavaScript in various programming scenarios.