Top k, medians and streaming data

The heap's best use is data you cannot or should not hold all at once.

Top k largest, with a min-heap

Counter-intuitively, you keep the k largest in a min-heap, so the weakest survivor is always at the top and cheapest to evict.

function topK(stream, k) {
  const heap = new MinHeap();     // holds the k largest seen so far

  for (const value of stream) {
    if (heap.size < k) heap.push(value);
    else if (value > heap.peek()) { heap.pop(); heap.push(value); }
  }

  return heap;
}

O(n log k) time and O(k) space, whatever n is. Sorting the whole input would be O(n log n) and require all of it in memory — impossible for a stream.

The rule of thumb: min-heap for the k largest, max-heap for the k smallest. Getting this backwards is the standard slip.

Running median with two heaps

Keep a max-heap of the lower half and a min-heap of the upper half, balanced to within one element. The median is then at one or both tops.

class RunningMedian {
  #low = new MaxHeap();     // smaller half
  #high = new MinHeap();    // larger half

  add(value) {
    this.#low.push(value);
    this.#high.push(this.#low.pop());              // pass the largest of low up

    if (this.#high.size > this.#low.size) {        // rebalance
      this.#low.push(this.#high.pop());
    }
  }

  get median() {
    return this.#low.size > this.#high.size
      ? this.#low.peek()
      : (this.#low.peek() + this.#high.peek()) / 2;
  }
}

O(log n) per insert, O(1) per query. The push-then-pop-then-rebalance sequence keeps the two halves correct without any special cases.

Merging k sorted lists

Hold the current head of each list in a heap of size k:

// O(N log k) for N elements across k lists — far better than
// concatenating and sorting, which is O(N log N).

This is the core of external merge sort and of log aggregation across shards.

Choosing between heap and quickselect

For an in-memory array and a one-off query, quickselect. For a stream, a bounded memory budget, or repeated queries, the heap.