Coding

Heaps

Priority queue for top-k and streaming min/max.

Coding pattern

Overview

Heaps (priority queues) keep the smallest or largest element instantly available, making them ideal for 'top-k', streaming medians, and scheduling. You reach for one whenever you repeatedly need the current best without fully sorting.

How it works

Coding pattern

ClientDataServiceEdge

Step by step, with examples

1
Stream/array
- You need repeated min/max access.
2
Build heap
- Maintain the heap-order invariant.
3
Top-k
- Pop or peek the best element.
4
Result
- Return the k largest/smallest or a merged order.
- Example: Top-K, merge k lists

When to reach for it

Kth largest/smallest
Merging sorted streams
Scheduling by priority

Example problem

Kth largest element in an array.

Approach

Keep a min-heap of size k
Pop when it exceeds k; the root is the answer

Solution

// Using a size-k min-heap (sketch)
function kthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Complexity

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

Common pitfalls

Confusing min vs max heap
Heap size drift

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions