Priority Queue

Overview

A priority queue is an abstract data type where elements are served based on priority rather than insertion order. Unlike a regular queue (FIFO), a priority queue always removes the element with the highest (or lowest) priority first, regardless of when it was inserted.

Priority queues are typically implemented using heaps (binary heap, Fibonacci heap) which provide efficient O(log n) insertion and O(log n) removal of the highest priority element, with O(1) access to the top element. They're essential for problems involving scheduling, finding K largest/smallest elements, and many graph algorithms like Dijkstra's shortest path.

Key characteristics:

• Priority-based - Elements ordered by priority, not insertion order
• Heap-based - Usually implemented with binary heap
• O(log n) operations - Insert and remove operations
• O(1) peek - Access top element in constant time
• Flexible ordering - Can be min-heap or max-heap

How Priority Queue Works

Priority queue maintains elements in a heap structure:

1. Heap property - Parent node has higher (or lower) priority than children
2. Complete binary tree - All levels filled except possibly last
3. Insert - Add element and bubble up to maintain heap property
4. Remove - Remove top element, replace with last, bubble down
5. Peek - Access root element (O(1))

The heap ensures the highest priority element is always at the root.

Min Heap vs Max Heap

Min Heap (Smallest Priority First)

Root is minimum element. Parent ≤ children.

class MinHeap<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;
  
  constructor(compareFn?: (a: T, b: T) => number) {
    this.compare = compareFn || ((a: T, b: T) => (a as number) - (b as number));
  }
  
  private parent(i: number): number {
    return Math.floor((i - 1) / 2);
  }
  
  private left(i: number): number {
    return 2 * i + 1;
  }
  
  private right(i: number): number {
    return 2 * i + 2;
  }
  
  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
  
  insert(val: T): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  private bubbleUp(i: number): void {
    while (i > 0 && this.compare(this.heap[i], this.heap[this.parent(i)]) < 0) {
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }
  
  extractMin(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return min;
  }
  
  private bubbleDown(i: number): void {
    while (true) {
      let smallest = i;
      const left = this.left(i);
      const right = this.right(i);
      
      if (left < this.heap.length && this.compare(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      
      if (right < this.heap.length && this.compare(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }
      
      if (smallest === i) break;
      
      this.swap(i, smallest);
      i = smallest;
    }
  }
  
  peek(): T | undefined {
    return this.heap[0];
  }
  
  size(): number {
    return this.heap.length;
  }
  
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
}

Time: O(log n) insert/extract, O(1) peek

Max Heap (Largest Priority First)

Root is maximum element. Parent ≥ children.

class MaxHeap<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;
  
  constructor(compareFn?: (a: T, b: T) => number) {
    this.compare = compareFn || ((a: T, b: T) => (b as number) - (a as number));
  }
  
  // Same structure as MinHeap, but compare reversed
  insert(val: T): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  private bubbleUp(i: number): void {
    while (i > 0 && this.compare(this.heap[i], this.heap[this.parent(i)]) > 0) {
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }
  
  extractMax(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return max;
  }
  
  // ... similar bubbleDown with reversed comparison
}

Note: Max heap uses reversed comparison (parent ≥ children).

Using Built-in Priority Queue (JavaScript/TypeScript)

JavaScript doesn't have built-in priority queue, but you can use a library or implement one:

Using Array with Manual Heap Operations

class PriorityQueue<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;
  
  constructor(compareFn: (a: T, b: T) => number) {
    this.compare = compareFn;
  }
  
  enqueue(item: T): void {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }
  
  dequeue(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    
    const top = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return top;
  }
  
  peek(): T | undefined {
    return this.heap[0];
  }
  
  size(): number {
    return this.heap.length;
  }
  
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
  
  // Helper methods (bubbleUp, bubbleDown, parent, left, right)
}

Pattern 1: K Largest Elements

Find K largest elements using min heap:

function findKLargest(nums: number[], k: number): number[] {
  const minHeap = new MinHeap<number>();
  
  for (const num of nums) {
    minHeap.insert(num);
    
    // Keep only K largest
    if (minHeap.size() > k) {
      minHeap.extractMin();
    }
  }
  
  const result: number[] = [];
  while (!minHeap.isEmpty()) {
    result.push(minHeap.extractMin()!);
  }
  
  return result.reverse(); // Largest to smallest
}

Time: O(n log k), Space: O(k)

Key insight: Use min heap of size K to track K largest elements.

Pattern 2: K Smallest Elements

Find K smallest elements using max heap:

function findKSmallest(nums: number[], k: number): number[] {
  const maxHeap = new MaxHeap<number>();
  
  for (const num of nums) {
    maxHeap.insert(num);
    
    // Keep only K smallest
    if (maxHeap.size() > k) {
      maxHeap.extractMax();
    }
  }
  
  const result: number[] = [];
  while (!maxHeap.isEmpty()) {
    result.push(maxHeap.extractMax()!);
  }
  
  return result.reverse(); // Smallest to largest
}

Time: O(n log k), Space: O(k)

Key insight: Use max heap of size K to track K smallest elements.

Pattern 3: Merge K Sorted Lists

Merge K sorted linked lists using priority queue:

class ListNode {
  val: number;
  next: ListNode | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const pq = new PriorityQueue<ListNode>((a, b) => a.val - b.val);
  
  // Add first node of each list
  for (const list of lists) {
    if (list) pq.enqueue(list);
  }
  
  const dummy = new ListNode(0);
  let current = dummy;
  
  while (!pq.isEmpty()) {
    const node = pq.dequeue()!;
    current.next = node;
    current = current.next;
    
    // Add next node from same list
    if (node.next) {
      pq.enqueue(node.next);
    }
  }
  
  return dummy.next;
}

Time: O(n log k) where n is total nodes, k is number of lists

Pattern 4: Top K Frequent Elements

Find K most frequent elements:

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  
  // Count frequencies
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  // Min heap of size K
  const pq = new PriorityQueue<[number, number]>(
    (a, b) => a[1] - b[1] // Compare by frequency
  );
  
  for (const [num, count] of freq) {
    pq.enqueue([num, count]);
    
    if (pq.size() > k) {
      pq.dequeue();
    }
  }
  
  const result: number[] = [];
  while (!pq.isEmpty()) {
    result.push(pq.dequeue()![0]);
  }
  
  return result.reverse();
}

Time: O(n log k), Space: O(n + k)

Pattern 5: Find Median from Data Stream

Maintain two heaps for median:

class MedianFinder {
  private maxHeap = new MaxHeap<number>(); // Lower half
  private minHeap = new MinHeap<number>();   // Upper half
  
  addNum(num: number): void {
    // Add to appropriate heap
    if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()!) {
      this.maxHeap.insert(num);
    } else {
      this.minHeap.insert(num);
    }
    
    // Balance heaps
    if (this.maxHeap.size() > this.minHeap.size() + 1) {
      this.minHeap.insert(this.maxHeap.extractMax()!);
    } else if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.insert(this.minHeap.extractMin()!);
    }
  }
  
  findMedian(): number {
    if (this.maxHeap.size() === this.minHeap.size()) {
      return (this.maxHeap.peek()! + this.minHeap.peek()!) / 2;
    } else {
      return this.maxHeap.peek()!;
    }
  }
}

Time: O(log n) add, O(1) find median

Key insight: Keep lower half in max heap, upper half in min heap.

Pattern 6: Task Scheduler

Schedule tasks with priorities:

interface Task {
  id: number;
  priority: number;
  name: string;
}

class TaskScheduler {
  private pq = new PriorityQueue<Task>(
    (a, b) => b.priority - a.priority // Higher priority first
  );
  
  addTask(task: Task): void {
    this.pq.enqueue(task);
  }
  
  processNext(): Task | undefined {
    return this.pq.dequeue();
  }
  
  hasTasks(): boolean {
    return !this.pq.isEmpty();
  }
}

Use case: Process tasks by priority order

Pattern 7: Dijkstra's Algorithm (Shortest Path)

Priority queue for finding shortest paths:

function dijkstra(graph: number[][][], start: number): number[] {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  
  const pq = new PriorityQueue<[number, number]>(
    (a, b) => a[1] - b[1] // Compare by distance
  );
  
  pq.enqueue([start, 0]);
  
  while (!pq.isEmpty()) {
    const [node, distance] = pq.dequeue()!;
    
    if (distance > dist[node]) continue;
    
    for (const [neighbor, weight] of graph[node]) {
      const newDist = dist[node] + weight;
      
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        pq.enqueue([neighbor, newDist]);
      }
    }
  }
  
  return dist;
}

Time: O((V + E) log V), Space: O(V)

Key insight: Always process node with minimum distance first.

When to Use Priority Queue

Use priority queue when you see these signals:

• "K largest" or "K smallest" - Find K extremum elements
• "Top K" - Top K frequent, top K closest, etc.
• "Priority" - Process by priority, not order
• "Shortest path" - Dijkstra's algorithm
• "Merge K sorted" - Merge multiple sorted sequences
• "Median" - Find median from stream
• "Scheduling" - Task/job scheduling by priority

Key distinction:

• Priority Queue - Process by priority, O(log n) operations
• Regular Queue - Process by insertion order, O(1) operations
• Stack - Process by reverse order, O(1) operations

Priority Queue vs Regular Queue

| Aspect | Priority Queue | Regular Queue |

|--------|---------------|---------------|

| Order | Priority-based | Insertion order (FIFO) |

| Operations | O(log n) insert/remove | O(1) enqueue/dequeue |

| Use case | K largest/smallest, scheduling | BFS, level-order |

| Implementation | Heap | Linked list, array |

| Peek | Highest priority element | First inserted element |

Remember:

• Priority queue for priority-based processing, K extremum problems
• Regular queue for FIFO processing, BFS, level-order

Template (Min Heap Priority Queue)

class PriorityQueueTemplate<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;
  
  constructor(compareFn: (a: T, b: T) => number) {
    this.compare = compareFn;
  }
  
  enqueue(item: T): void {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }
  
  dequeue(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    
    const top = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return top;
  }
  
  peek(): T | undefined {
    return this.heap[0];
  }
  
  size(): number {
    return this.heap.length;
  }
  
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
  
  // Helper methods: bubbleUp, bubbleDown, parent, left, right
}

Template (K Largest Elements)

function kLargestTemplate<T>(items: T[], k: number, compare: (a: T, b: T) => number): T[] {
  const pq = new PriorityQueueTemplate<T>(compare);
  
  for (const item of items) {
    pq.enqueue(item);
    
    if (pq.size() > k) {
      pq.dequeue();
    }
  }
  
  const result: T[] = [];
  while (!pq.isEmpty()) {
    result.push(pq.dequeue()!);
  }
  
  return result.reverse();
}

Time and Space Complexity

Heap Operations

• insert: O(log n)
• extractMin/extractMax: O(log n)
• peek: O(1)
• size: O(1)
• isEmpty: O(1)
• Space: O(n)

Common Patterns

• K largest/smallest: O(n log k)
• Merge K sorted lists: O(n log k) where n is total elements
• Top K frequent: O(n log k)
• Dijkstra's algorithm: O((V + E) log V)

Note: Heap operations are O(log n) because tree height is O(log n).

Practice Tips

1. Choose right heap - Min heap for K largest, max heap for K smallest
2. Heap size K - Keep heap size K for K largest/smallest problems
3. Custom comparator - Use comparator function for custom ordering
4. Bubble up/down - Understand heapify operations
5. Array indexing - Parent: (i-1)/2, Left: 2i+1, Right: 2i+2
6. Two heaps - Use two heaps for median problems
7. Update priority - May need to re-insert with new priority

Common Mistakes

1. Wrong heap type - Using min heap for K largest (should be max)
2. Heap size too large - Not limiting heap size to K
3. Wrong comparator - Comparator logic reversed
4. Not re-heapifying - Forgetting to bubble up/down after changes
5. Index errors - Off-by-one in parent/child calculations
6. Empty heap - Not checking isEmpty before dequeue
7. Memory leaks - Not clearing heap when done

Real-World Applications

Priority queues are used extensively in:

• Operating Systems - Process scheduling, task prioritization
• Networking - Packet routing, quality of service
• Graph Algorithms - Dijkstra's, Prim's, A* search
• Data Compression - Huffman coding
• Event Simulation - Discrete event simulation
• Load Balancing - Server load balancing
• Search Engines - Ranking search results
• Gaming - AI decision making, pathfinding

Related Concepts

• Heap - Data structure used to implement priority queue
• Binary Heap - Most common heap implementation
• Dijkstra's Algorithm - Uses priority queue for shortest path
• K Largest/Smallest - Common priority queue problems
• Merge K Sorted - Priority queue pattern
• Median - Two-heap approach

Summary

Priority queue is a data structure for priority-based processing:

• Priority-based - Elements ordered by priority, not insertion order
• Heap-based - Usually implemented with binary heap
• O(log n) operations - Insert and remove operations
• O(1) peek - Access top element in constant time
• Essential - For K extremum problems, scheduling, graph algorithms

Key takeaways:

• Use min heap for K largest, max heap for K smallest
• Keep heap size K for K extremum problems
• Custom comparator for flexible ordering
• Essential for Dijkstra's algorithm and scheduling
• Foundation for many advanced algorithms

Mastering priority queue will help you solve K largest/smallest, scheduling, and graph algorithm problems efficiently in coding interviews.