Sometimes items must be processed by priority rather than arrival time. A priority queue exposes the item with the highest priority at each removal, while a normal queue always removes the oldest item.
Ordering by priority
Removal returns the item with the highest priority among those currently in the queue. A minimum priority queue returns the smallest value first. A maximum priority queue returns the largest value first. I needed this ordering while scheduling tasks because a FIFO queue always removes the oldest item. I compared an array scan with a heap.
Array and heap implementations
My first array implementation stores each item and searches for the smallest priority on every dequeue:
class PriorityQueueArray {
constructor() {
this.queue = [];
}
enqueue(item, priority) {
this.queue.push({ item, priority });
}
dequeue() {
if (this.isEmpty()) return null;
// Find highest priority (lowest number for min-priority)
let highestPriorityIndex = 0;
for (let i = 1; i < this.queue.length; i++) {
if (this.queue[i].priority < this.queue[highestPriorityIndex].priority) {
highestPriorityIndex = i;
}
}
return this.queue.splice(highestPriorityIndex, 1)[0];
}
isEmpty() {
return this.queue.length === 0;
}
}
The array version is easy to understand, but dequeue is O(n) because it scans the array and then removes an element.
The heap version keeps the smallest priority at the root. Insertion moves the new item upward, and removal moves the replacement root downward. Both operations take O(log n):
class MinHeap {
constructor() {
this.heap = [];
}
enqueue(item, priority) {
this.heap.push({ item, priority });
this.bubbleUp(); // Maintain heap property
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].priority >= this.heap[parentIndex].priority) break;
// Swap with parent
[this.heap[index], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[index],
];
index = parentIndex;
}
}
dequeue() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const root = this.heap[0];
this.heap[0] = this.heap.pop();
this.sinkDown(0); // Maintain heap property
return root;
}
sinkDown(index) {
const length = this.heap.length;
const element = this.heap[index];
while (true) {
const leftIndex = 2 * index + 1;
const rightIndex = 2 * index + 2;
let swapIndex = null;
// Find smaller child
if (
leftIndex < length &&
this.heap[leftIndex].priority < element.priority
) {
swapIndex = leftIndex;
}
if (
rightIndex < length &&
this.heap[rightIndex].priority <
(swapIndex === null
? element.priority
: this.heap[leftIndex].priority)
) {
swapIndex = rightIndex;
}
if (swapIndex === null) break;
[this.heap[index], this.heap[swapIndex]] = [
this.heap[swapIndex],
this.heap[index],
];
index = swapIndex;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
Both enqueue and dequeue are O(log n) in this implementation.
Complexity and common uses
I find priority queues useful for Dijkstra's shortest path algorithm, task scheduling, event simulation, and merging k sorted lists. Each task repeatedly needs the smallest or largest remaining item.
The array version uses O(n) removal time and O(n) storage. The heap version keeps O(log n) enqueue and dequeue operations, with O(n) storage. A heap adds implementation work, but it avoids scanning every item for each removal.
Priority queues make the ordering rule explicit. Choose a min or max heap based on the required priority, then use the heap when repeated removals must stay logarithmic.
Loading comments...