The K Smallest Things

"Find the k largest" tempts everyone toward sorting: sort, take the first k, done. That answer costs O(n log n) time and, worse, O(n) memory on a stream that never ends. The heap answer costs O(log k) per element, O(k) memory, and never needs to see the whole input at once — which is why it is the answer interviews are actually fishing for when they say "stream".

A heap is a podium, not a ranking

The trick has one sentence in it: the kth largest of everything seen is the smallest thing among the k largest. So keep exactly the k largest in a min-heap — minimum on top — and the top of the heap is the answer by construction.

export class KthLargest {
  readonly #k: number
  readonly #topK: MinHeap

  add(value: number): number {
    if (this.#topK.size < this.#k) {
      this.#topK.push(value)
    } else if (value > this.#topK.peek()) {
      this.#topK.pop() // whoever falls off the podium
      this.#topK.push(value)
    }
    return this.#topK.peek()
  }
}

The comparison does the filtering: a value at or below the podium's minimum cannot be in the top k, and is discarded without being stored. That is where the memory bound comes from — not from a clever allocation, from a comparison that refuses work. Note the direction flip that confuses everyone at first: k largest keeps a min-heap, because the element you must be able to evict quickly is the smallest of the kept ones. For k smallest, flip everything — max-heap, compare the other way.

} else if (value > this.#topK.peek()) {
  this.#topK.()
  this.#topK.push(value)
}

The array IS the tree

A binary heap stores its tree implicitly in an array: children of index i live at 2i + 1 and 2i + 2, the parent at ⌊(i − 1) / 2⌋. No pointers, no node objects — the shape rule (fill levels left to right) guarantees the arithmetic stays honest.

#siftDown(index: number): void {
  for (;;) {
    const left = 2 * index + 1
    const right = 2 * index + 2
    let smallest = index
    if (left < this.#values.length && (this.#values[left] as number) < (this.#values[smallest] as number)) {
      smallest = left
    }
    if (right < this.#values.length && (this.#values[right] as number) < (this.#values[smallest] as number)) {
      smallest = right
    }
    if (smallest === index) break
    // swap values[index] and values[smallest]; continue from smallest
  }
}

push appends and sifts up (the new leaf walks toward the root while smaller than its parent); pop moves the last leaf to the root and sifts down. The one line that carries the most bugs is in sift-down: a parent must sink below its smaller child — and the smaller child is sometimes the right one. Checking only the left child produces a heap that works on symmetric inputs and misorders on exactly the shapes where the right subtree is lighter.

#siftDown(index: number): void {
  const left = 2 * index + 1
  const right = 2 * index + 
  let smallest = index
  // compare against BOTH children before deciding to stay
}

Ties, and counting your way to order

For "most frequent k words", a hash map counts first, then ordering decides: higher count first, and among equal counts the alphabetically smaller word first — the tie rule is part of the contract, not a detail. A heap of size k works here too, with a comparator that encodes both rules; so does the simpler sort-after-counting when the input is finite. What is not acceptable is sorting the original input — the counts are the thing being ranked, and ranking a different array than you counted is a classic silent zero.

How to debug a heap

Assert the two invariants after every mutating operation: values[0] is the minimum, and every parent is at most its children. Two lines, and they catch every sift bug at the operation that caused it instead of three pops later. When an invariant fails, print the array as the tree it secretly is — indices with their values, indented by level; the violation is always a parent-child pair, and the indentation makes it jump out. For top-k, print the podium on every arrival: it should only ever change when a value beats its minimum, and it should never grow past k. In the exercises for this concept, the sift-down review is deliberate: its hidden tests are exactly the shapes where the right child is the smaller one.

Where this bites

• A max-heap for k largest. The eviction logic inverts — you end up evicting the best and keeping the worst, and the answer is plausible-looking garbage. Counter: say which element you must evict fastest; that element sits on top, and its kind names the heap.
• Sifting against one child. Two-children trees where the right side is lighter get misordered, and tests with symmetric data pass. Counter: compare against both children and take the smaller — or better, assert the heap invariant after every op so the shape that breaks it fails immediately.
• Pop without the last-leaf move. Popping the root and compacting leaves a hole or an unordered array; the pattern is always swap-last-to-root, then sift down. Counter: the array length must shrink by exactly one per pop, and index 0 must hold the extrema the instant pop returns.
• Sorting when the input is a stream. Sort-based answers hold everything and answer nothing until the end — on a stream they hold everything forever. Counter: if the question's noun is "so far" or "after each arrival", the structure is size-k by requirement, not preference.