In JavaScript, a priority queue is an abstract data type similar to a regular queue but with the added feature of each element having a priority associated with it. Elements with higher priority are dequeued before elements with lower priority, regardless of the order in which they were added. Priority queues are commonly used in various applications such as task scheduling, shortest path algorithms, and data compression.
Operations:
Enqueue (Insertion):
- Adds an element to the priority queue with a specified priority.
- The element is inserted based on its priority so that elements with higher priority are dequeued first.
Dequeue (Extraction):
- Removes and returns the element with the highest priority from the priority queue.
- If multiple elements have the same highest priority, the one that was enqueued first is dequeued first.
Peek:
- Returns the element with the highest priority from the priority queue without removing it.
- Useful for checking the next element to be dequeued without actually dequeuing it.
isEmpty:
- Checks if the priority queue is empty.
Implementation:
Priority queues can be implemented using various data structures, such as arrays, linked lists, binary heaps, or binary search trees. One common approach is to use a binary heap, which provides efficient insertion and removal operations while maintaining the priority order.
Here’s a basic example implementation of a priority queue using an array and JavaScript’s built-in
Array.prototype.sort()method:
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(element, priority) {
this.queue.push({ element, priority });
this.queue.sort((a, b) =>
a.priority - b.priority);
}
dequeue() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.queue.shift().element;
}
peek() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.queue[0].element;
}
isEmpty() {
return this.queue.length === 0;
}
}
// Example usage:
let pq = new PriorityQueue();
pq.enqueue("Task 1", 2);
pq.enqueue("Task 2", 1);
pq.enqueue("Task 3", 3);
console.log(pq.dequeue());
// Output: Task 2 (Task 2 has the highest priority)
console.log(pq.peek());
// Output: Task 1 (Task 1 is next in priority)
Complexity:
Enqueue (Insertion):
- The time complexity for inserting an element with a specified priority is O(log n) if using a binary heap or O(n) if using other data structures.
Dequeue (Extraction):
- The time complexity for removing the element with the highest priority is O(log n) if using a binary heap or O(1) if using other data structures.
