🚀 Priority Queue Patterns

Priority Queues (Heaps) are the "secret weapon" for any problem involving K items or Rankings.

💡 The Logic (ELI5)

Think of a Leaderboard:

You have a game with 1,000 players.
You only care about the Top 10.
You don't need to sort all 1,000 players every time someone scores.
You just keep the Top 10 in a small "Bucket" (Heap).
If someone gets a score higher than the lowest person in your Top 10, they kick that person out and join the bucket!

🔍 The Deep Dive

Pattern 1: Top K Elements

Goal: Find the K largest/smallest elements.
Strategy: Use a Min-Heap of size K for "K Largest". The root will always be the smallest of your "Elite Top K", making it easy to replace.
Complexity: $O(n \log k)$.

Pattern 2: K-Way Merge

Goal: Merge K sorted streams into one.
Strategy: Put the first element of each stream into a Min-Heap. Extract min, and push the next element from that specific stream into the heap.
Complexity: $O(n \log k)$.

Pattern 3: Median Finder

Goal: Find the median in a live stream of data.
Strategy: Use two heaps. A Max-Heap for the smaller half and a Min-Heap for the larger half. The middle elements will always be at the roots!

🛠️ Code Forge: K-th Largest Element

This is a classic LeetCode Medium/Hard pattern.


javascript Standard
/**
 * Find Kth largest in O(N log K) using a Min-Heap
 */
function findKthLargest(nums, k) {
  const minHeap = new MinPriorityQueue(); // Hypothetical class

  for (let num of nums) {
    minHeap.push(num);
    if (minHeap.size() > k) {
      minHeap.pop(); // Remove the smallest of our current Top K
    }
  }

  return minHeap.peek(); // The k-th largest is at the root
}

🎯 Interview Pulse

Visualizing the Heap

If the question is "K Smallest", use a Max-Heap. If the question is "K Largest", use a Min-Heap. Why? Because the root of a Min-Heap is its smallest element. If you have K elements and you want the "Largest", checking if a new number is bigger than the smallest member of the elite club is the fastest check.

Priority Queue Problems