Priority Queue

What is a Priority Queue?

A Priority Queue is an abstract data type where each element has a priority value, and elements are served based on priority rather than insertion order. Unlike a standard queue (FIFO), higher-priority elements are dequeued before lower-priority ones, regardless of when they were added.

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

Visual Example (Max-Heap Priority Queue)

Operation sequence:

  1. insert("A", 3): [(A,3)]
  2. insert("B", 5): [(A,3), (B,5)] → [(B,5), (A,3)]
  3. insert("C", 1): [(B,5), (A,3), (C,1)]
  4. extractMax(): Returns "B" → [(A,3), (C,1)]
  5. insert("D", 4): [(A,3), (C,1), (D,4)] → [(D,4), (A,3), (C,1)]
  6. extractMax(): Returns "D" → [(A,3), (C,1)]

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

Time Complexity

  • insert(): O(log n) (heap), O(1) amortized (Fibonacci heap)
  • extractMax()/extractMin(): O(log n)
  • peek(): O(1)
  • delete(item): O(log n) (heap), O(1) amortized (Fibonacci heap)
  • changePriority(): O(log n)

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

The priority queue is a fundamental data structure that enables efficient management of elements based on their importance or urgency. Its ability to always provide access to the highest (or lowest) priority item makes it indispensable in algorithms where processing order significantly impacts performance or correctness. The choice of implementation (heap, BST, etc.) depends on the specific application's requirements for insertion, extraction, and auxiliary operations.

Visualize Priority Queue Operations with Animations

Priority Queue is empty
Highest PriorityLowest Priority
Priority Queue is empty

Test Your Knowledge before moving forward!

Queue Quiz Challenge

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)

Double Ended 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

Explore Other Types

Single Ended Queue

Circular Queue

Double-Ended Queue

Multiple Queue