Stop 21 · Data Structures & AlgorithmsTopics · 7/17

Heap

In short

"Top K", "K closest", "merge K sorted lists": when you see a K, think heap. It always hands you the smallest (or largest) item without sorting everything.

A tree-based structure that keeps the minimum (or maximum) element quickly accessible — the engine behind priority queues, used for 'top K' and scheduling problems.

The purple blob nurse waves a patient with a bandaged arm ahead of others waiting.

Think of it like this

The emergency ward

Patients aren't seen in arrival order. A broken arm goes before a mild cold, even if the cold came first. The nurse always calls the most urgent case next. That's a priority queue, and a heap is how it's built.

Watch it happen

Pushing 1 into a min-heap

1 (new)

1/5In a min-heap every parent is smaller than its children, so the minimum, 3, sits at the top.

The big ideas

What you need to know

Min at the top

A min-heap keeps the smallest item at the root. Reading it is O(1); push and pop are O(log n).

Stored as an array

For index i, children live at 2i + 1 and 2i + 2, and the parent at floor((i - 1) / 2). No pointers needed.

Top K trick

For the K largest items, keep a min-heap of size K. If a new item beats the root, swap it in.

No built-in in JavaScript

JS has no heap class. Interviewers usually let you assume one, or write a short version like below.

See it in code

Walk through the code

1class MinHeap {2  private a: number[] = [];3 4  push(x: number) {5    this.a.push(x);6    let i = this.a.length - 1;7    while (i > 0) {8      const parent = Math.floor((i - 1) / 2);9      if (this.a[parent] <= this.a[i]) break;10      [this.a[parent], this.a[i]] = [this.a[i], this.a[parent]];11      i = parent;12    }13  }14 15  peek() { return this.a[0]; }16}

1/4Add the new value at the end of the array, the next free spot.

This is the "bubble up" half of a heap. pop() does the opposite: move the last item to the root and sink it down.

Save yourself the pain

Common mistakes

Oops

Sorting the whole array to get the top 3 out of a million items.

Do this instead

A size-K heap does it in O(n log K), and only keeps K items in memory.

Oops

Thinking a heap is fully sorted.

Do this instead

Only the parent-child rule holds. Siblings can be in any order; only the root is guaranteed.

Your mission

Heap in action

~40 min

Quick check

You need the 10 highest scores from 1 crore results. Which approach uses the least memory?

Go deeper

1Solve a 'find the K largest/smallest elements' problem using a heap.
2Learn the difference between a min-heap and a max-heap.
3Recognize heap-shaped problems: anything about 'top K', 'kth largest', or merging sorted data.