What is an efficient way to implement a priority queue in JavaScript?
Priority queues consist of entries that have both a priority value and associated data. When adding a new element, it should “bubble up” if it has a higher priority than existing elements in the collection. When calling the pop method, we should retrieve the data for the element with the highest priority.
Is it sensible to create a PriorityQueue class with two methods, push and pop, that take two parameters (data and priority)? While that concept makes sense, I’m uncertain about the best underlying data structure to use for manipulating the ordering of elements. Should I just use an array and iterate through it to find the element with the maximum priority, or is there a more efficient approach?
What’s a good way to implement a javascript priority queue?
An efficient way to approach a JavaScript priority queue is by using a Min-Heap or Max-Heap structure. Heaps are particularly well-suited for managing priorities due to their hierarchical organization, where the root element (either minimum or maximum) can be accessed in constant time. This is an improvement over arrays, as heap insertion and deletion both have logarithmic complexity O(log n), making them scalable and fast.
Here’s a basic example of a priority queue class using a max-heap:
class PriorityQueue {
constructor() {
this.heap = [];
}
push(data, priority) {
const node = { data, priority };
this.heap.push(node);
this.bubbleUp();
}
pop() {
if (this.heap.length === 0) return null;
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.bubbleDown();
}
return max.data;
}
bubbleUp() {
let index = this.heap.length - 1;
const element = this.heap[index];
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (element.priority <= parent.priority) break;
this.heap[index] = parent;
index = parentIndex;
}
this.heap[index] = element;
}
bubbleDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild.priority > element.priority) swap = leftChildIndex;
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild.priority > element.priority) ||
(swap !== null && rightChild.priority > leftChild.priority)
) swap = rightChildIndex;
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
index = swap;
}
this.heap[index] = element;
}
}
This class allows push and pop operations with efficient element organization, ideal for scenarios where maintaining an ordered queue is necessary.
I’ve worked a bit on alternative structures for priority queues, and another effective method for a JavaScript priority queue is using a Sorted Linked List. This approach focuses on maintaining order directly upon insertion, ensuring that removal of the highest-priority element is extremely efficient. While insertion does take linear time O(n), this trade-off can be worth it if pop is your most frequent operation.
class Node {
constructor(data, priority) {
this.data = data;
this.priority = priority;
this.next = null;
}
}
class PriorityQueue {
constructor() {
this.head = null;
}
push(data, priority) {
const newNode = new Node(data, priority);
if (!this.head || this.head.priority < priority) {
newNode.next = this.head;
this.head = newNode;
} else {
let current = this.head;
while (current.next && current.next.priority >= priority) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
pop() {
if (!this.head) return null;
const data = this.head.data;
this.head = this.head.next;
return data;
}
}
This linked list implementation is intuitive and keeps pop in constant time O(1). For certain applications, such as event-driven systems or task management in JavaScript, this is a great structure to consider.
For a strong JavaScript priority queue, the sorted linked list offers a great balance of simplicity and access time, but another enhancement is worth noting. Depending on the use case, you could also wrap the linked list within a custom class that supports an optimized insertion for frequently used priorities. This approach combines predictable insertion with O(1) access to high-priority items.
class Node {
constructor(data, priority) {
this.data = data;
this.priority = priority;
this.next = null;
}
}
class PriorityQueue {
constructor() {
this.head = null;
}
push(data, priority) {
const newNode = new Node(data, priority);
if (!this.head || this.head.priority < priority) {
newNode.next = this.head;
this.head = newNode;
} else {
let current = this.head;
while (current.next && current.next.priority >= priority) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
pop() {
if (!this.head) return null;
const data = this.head.data;
this.head = this.head.next;
return data;
}
}
With a few tweaks, such as adding a lookup for top priority ranges, the linked list can support near O(1) access for a more varied priority spread, making it a versatile solution for different JavaScript priority queue needs.