Heaps: always the smallest next

A heap hands you the smallest item, or the largest, at any moment. Adding or removing an item costs only O(log n): about 20 steps for a million items. Reach for one whenever a problem keeps asking “what's the smallest next?” while items keep arriving.

Think of it like this: a hospital emergency room. Patients arrive in any order, but the next one seen is always the most urgent. Nobody re-sorts the whole waiting room when someone new walks in. The staff compare the newcomer with a few people and slot them in.

How to spot it

Words and constraints in a problem that point to this pattern:

• “The k largest”, “the k smallest”, “the top k most frequent”, “the kth largest”
• “Repeatedly take the two smallest (or largest) and combine them”
• “Merge k sorted lists or arrays”
• A stream of numbers where you keep answering “what's the smallest so far?”
• Scheduling: “the next meeting to end”, “the next task to run”, “the closest points”

Watch it work

The template

class MinHeap<T> {
  private items: T[] = [];  // the tree, stored level by level

  // less(a, b) is true when a should come out before b. The default: smaller numbers first.
  constructor(private less: (a: T, b: T) => boolean = (a, b) => (a as unknown as number) < (b as unknown as number)) {}

  get size(): number {
    return this.items.length;
  }

  peek(): T | undefined {
    return this.items[0];  // the root is always the item that comes out first
  }

  push(item: T): void {
    this.items.push(item);                      // the next free spot in the bottom row
    let i = this.items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.less(this.items[i], this.items[parent])) break; // parent is fine: stop
      this.swap(i, parent);                     // bubble up one level
      i = parent;
    }
  }

  pop(): T | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];                  // the answer
    const last = this.items.pop()!;             // take the last item off the end
    if (this.items.length > 0) {
      this.items[0] = last;                     // and move it into the root's place
      let i = 0;
      while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let first = i;                          // whichever of i, left, right should be on top
        if (left < this.items.length && this.less(this.items[left], this.items[first])) first = left;
        if (right < this.items.length && this.less(this.items[right], this.items[first])) first = right;
        if (first === i) break;                 // both children are fine: stop
        this.swap(i, first);                    // bubble down towards the smaller child
        i = first;
      }
    }
    return top;
  }

  private swap(a: number, b: number): void {
    [this.items[a], this.items[b]] = [this.items[b], this.items[a]];
  }
}

// Usage
const h = new MinHeap<number>();
[5, 3, 8, 1].forEach((x) => h.push(x));
h.pop(); // 1
h.pop(); // 3
const maxFirst = new MinHeap<number>((a, b) => a > b); // largest comes out first

Worked example

1. The first idea: sort every point by distance and take the first k. That's O(n log n). It's fine for small inputs, but with 1,000,000 points and k = 10 it sorts 999,990 points you'll never return.

   function kClosestSorted(points: [number, number][], k: number): [number, number][] {
     const dist = (p: [number, number]) => p[0] * p[0] + p[1] * p[1];
     return [...points].sort((a, b) => dist(a) - dist(b)).slice(0, k);
   }
   

2. Notice what you really need. You need the k best points so far, and fast access to the worst of them. Then you can throw it out when a closer point arrives. “Quick access to the worst of k” is a heap whose top is the farthest point.

3. Compare with squared distance x * x + y * y. The square root doesn't change which point is closer, so you can skip Math.sqrt. Use the MinHeap class with less set to “farther comes out first”.

4. Push each point. Whenever the heap holds k + 1 points, pop: that removes the farthest of them. What's left at the end is the k closest.

   function kClosest(points: [number, number][], k: number): [number, number][] {
     const dist = (p: [number, number]) => p[0] * p[0] + p[1] * p[1];
     const heap = new MinHeap<[number, number]>((a, b) => dist(a) > dist(b)); // farthest on top
     for (const p of points) {
       heap.push(p);
       if (heap.size > k) heap.pop();  // too many: drop the farthest
     }
     const result: [number, number][] = [];
     while (heap.size > 0) result.push(heap.pop()!);
     return result;
   }
   

5. Run it. The squared distances are 18, 26, 20 and 2. Push 18 → push 26 → push 20, size 3 > 2, pop 26 → push 2, size 3, pop 20. Left: 18 and 2, which are [3, 3] and [1, 1]. Edge cases: if k is at least the number of points, nothing is popped and every point comes back. k = 0 pops after every push and returns [].

Common mistakes

• Using 1-based child formulas (2 * i and 2 * i + 1) on a 0-based array: index 0 becomes its own child, and the heap quietly stops being a heap.
• Bubbling down by always swapping with the left child instead of the smaller child: the bigger child becomes a parent of the smaller one, and a later pop returns the wrong item.
• Picking the wrong heap for top k: for the k largest, keep a min-heap so you can throw out the smallest. For the k smallest, keep a max-heap. Mixing them up throws away the best items.
• Re-sorting the whole array after every push to imitate a heap: each sort is O(n log n), so n pushes cost O(n² log n) and time out.
• Assuming JavaScript has a built-in priority queue: it doesn't. Be ready to write the class, or ask the interviewer whether you may assume one.

Cost

In interviews