Who Goes First?

A Priority Queue is a Queue where elements come out based on priority, not arrival time.

  • Emergency Room: Heart attack treated before stubbed toe.
  • OS Scheduler: High priority processes run first.

1. Hardware Truth: Cache Locality of Heaps

Why are heaps usually arrays even though they are logically trees?

The Comparison

  • Tree-based PQ (e.g., AVL/RB-Tree): Every node is a heap-allocated object. To traverse, the CPU must fetch pointers (Pointer Chasing), causing frequent Cache Misses.
  • Array-based Heap: All data is stored in a contiguous block of RAM. When the CPU fetches index i, it pre-fetches the surrounding memory (including children at 2i+1, 2i+2) into the L1/L2 Cache.

The Latency Impact

A cache miss to main RAM cost ~100ns. A hit in the L1 cache costs ~1ns. Array-based heaps can be 10-50x faster in practice than tree-based priority queues of the same size.

2. Top K Elements Pattern

Problem: Find the k largest elements in a stream/array.

  • Sort: O(N log N).
  • Min Heap: O(N log k). Keep a heap of size k. If x > root, pop root, push x.

3. Interactive: Top K Visualizer

Stream: [10, 5, 20, 3, 40], K = 3. Goal: Keep 3 largest.

Stream

Min Heap (Size 3)

Start...

4. Implementation

public int findKthLargest(int[] nums, int k) {
  PriorityQueue<Integer> heap = new PriorityQueue<>(); // Min Heap
  for (int n : nums) {
    heap.offer(n);
    if (heap.size() > k) {
      heap.poll(); // Remove smallest
    }
  }
  return heap.peek();
}

Deep Dive: Kth Largest Element

For a complete breakdown of the Selection Algorithm and a comparison between Heap and Quickselect approaches, visit the Problem Vault:

[!TIP] Vault: Kth Largest Element in an Array

Practice: Meeting Rooms II

Master the pattern of tracking concurrent events using a Min-Heap:

[!TIP] Vault: Meeting Rooms II

Practice: K Closest Points to Origin

See how Top K logic applies to 2D coordinates:

[!TIP] Vault: K Closest Points to Origin

Hard Practice: Minimum Cost to Hire K Workers

Test your ability to optimize complex constraints using Sorting and Max-Heaps:

[!TIP] Vault: Minimum Cost to Hire K Workers