Heap & Top K

How to think about it

A heap keeps the boundary of interest. For top K largest, a min-heap of size K stores the current winners; the root is the weakest winner. For streams, two heaps can balance lower/upper halves for the median.

Template shapes

Shape	Core move	Notes
Top K	Min-heap size K	Evict root if new is better
K-way merge	Min-heap of heads	Push next from same list
Median	Max-heap + min-heap	Rebalance sizes

Complexity baseline

O(n log k) typical for top-K; O(log n) per insert/pop. Space O(k) or O(n).

From template to problem

1. Clarify: K largest, K smallest, or K frequent?
2. Pick heap orientation so the root is the one you are ready to discard.
3. Process elements; maintain heap size ≤ K when applicable.
4. Extract or convert heap to the answer format.

/** Heap / top-K template: kth largest via min-heap of size k. */
export function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = [];
  for (const x of nums) {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap[0]!;
}

/** Heap / top-K template: kth largest via min-heap of size k. */
export function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = [];
  for (const x of nums) {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap[0]!;
}