Queue

Priority Queue

What is a Priority Queue?

A priority queue throws out the "first come, first served" rule that a normal queue follows. Every element carries a priority, and whichever element has the most urgent priority gets dequeued next — it doesn't matter how long it's been sitting there.

Key Characteristics

Priority queues have these fundamental properties:

  1. Priority-based ordering:
    • Elements are processed by priority (highest first or lowest first)
  2. Two core operations:
    • insert(item, priority) - Add with priority
    • extractMax()/extractMin() - Remove highest/lowest priority item
  3. Peek operation:
    • View highest/lowest priority item without removal
  4. No FIFO guarantee:
    • Equal priority elements may be processed in arbitrary order

Implementation Variations

Common implementation approaches:

  1. Binary Heap:
    • Most common implementation
    • O(log n) insert and extract
    • O(1) peek
    • Memory efficient
  2. Balanced Binary Search Tree:
    • O(log n) all operations
    • Supports more operations (like delete-by-value)
    • Higher memory overhead
  3. Array (Unsorted):
    • O(1) insert, O(n) extract
    • Simple but inefficient for large datasets
  4. Fibonacci Heap:
    • Amortized O(1) insert
    • O(log n) extract
    • Complex implementation

Applications

Priority queues are used in:

  • Dijkstra's Algorithm: Finding shortest paths in graphs
  • Huffman Coding: Data compression
  • Operating Systems: Process scheduling
  • Event-driven Simulation: Processing events in time order
  • A* Search: Pathfinding in AI
  • Bandwidth Management: Prioritizing network packets

Special Cases

Interesting priority queue variations:

  • Min-Priority Queue: Extracts minimum priority first
  • Max-Priority Queue: Extracts maximum priority first
  • Double-Ended Priority Queue: Supports both min and max extraction
  • Indexed Priority Queue: Allows priority updates by key
  • Bounded Priority Queue: Fixed capacity with eviction policies

What makes it so useful is that it always hands you the most important item on demand, which is exactly what a lot of algorithms need. Under the hood it's usually built on a heap, though a balanced BST works too — which one you pick depends on how the application balances insertion speed against extraction speed.

Daily DSA Challenge by Scale Engineer

Min-Priority Queue Visualiser (lower number = higher priority)

Priority queue is empty

Test Your Knowledge before moving forward!

Priority Queue Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Priority Queue Implementation

// Priority Queue Implementation in JavaScript (Min-Heap)
class PriorityQueue {
  constructor(comparator = (a, b) => a.priority - b.priority) {
    this.heap = [];
    this.comparator = comparator;
  }

  // Add element to the queue
  enqueue(value, priority) {
    const element = { value, priority };
    this.heap.push(element);
    this.bubbleUp(this.heap.length - 1);
  }

  // Remove and return the highest priority element
  dequeue() {
    if (this.isEmpty()) return null;
    const root = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return root.value;
  }

  // Peek at the highest priority element without removing it
  peek() {
    if (this.isEmpty()) return null;
    return this.heap[0].value;
  }

  // Get current size of the queue
  size() {
    return this.heap.length;
  }

  // Check if the queue is empty
  isEmpty() {
    return this.heap.length === 0;
  }

  // Move element up the heap to maintain heap property
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.comparator(this.heap[index], this.heap[parentIndex]) >= 0) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  // Move element down the heap to maintain heap property
  bubbleDown(index) {
    const lastIndex = this.heap.length - 1;
    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let smallestIndex = index;

      if (leftChildIndex <= lastIndex && 
          this.comparator(this.heap[leftChildIndex], this.heap[smallestIndex]) < 0) {
        smallestIndex = leftChildIndex;
      }

      if (rightChildIndex <= lastIndex && 
          this.comparator(this.heap[rightChildIndex], this.heap[smallestIndex]) < 0) {
        smallestIndex = rightChildIndex;
      }

      if (smallestIndex === index) break;
      [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
      index = smallestIndex;
    }
  }
}

// Usage
const pq = new PriorityQueue();
pq.enqueue("Task 1", 3);  // Lower numbers = higher priority
pq.enqueue("Task 2", 1);
pq.enqueue("Task 3", 2);

console.log(pq.dequeue()); // "Task 2" (highest priority)
console.log(pq.peek());    // "Task 3" (next highest priority)
console.log(pq.size());    // 2

Done With the Learning

Mark Priority Queue as done and view it on your dashboard

Explore Other Types

Single Ended Queue

Circular Queue

Double-Ended Queue

Multiple Queue