Stop 21 · Data Structures & AlgorithmsTopics · 7/17

Heap

In short

Need the smallest, the largest, or the top K of something, again and again? Sorting every time is wasteful. A heap keeps the winner at the top for you.

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 jaadu nurse wheels the most unwell patient to the front of the emergency ward.

Think of it like this

The hospital emergency ward

Patients aren't seen in arrival order. The most serious case is always taken next, and when a new serious case arrives, it moves up the list. A heap is that triage nurse.

Watch it happen

push(2) into a min-heap

1/4A valid min-heap. Every parent is smaller than its children, so the root, 1, is the minimum.

The big ideas

What you need to know

The top is always the min (or max)

In a min-heap, every parent is smaller than its children, so the smallest item sits at the root.

Fast where it matters

Peek is O(1). Insert and remove-top are O(log n), because items only move up or down one branch.

Stored in a plain array

For index i, children are at 2i+1 and 2i+2, and the parent is at Math.floor((i-1)/2).

JS has no built-in heap

In interviews you may write one, or say you'd use a library in real code. Ask which they prefer.

How it works

Top K largest with a min-heap of size K

1
Push each number
Add it to a min-heap.
2
Too big? Pop
If the heap holds more than K items, remove the smallest.
3
Keep going
The heap always holds the K largest seen so far.
4
Read the answer
The root is now the K-th largest number.

See it in code

Walk through the code

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

1/4Add the new value at the end of the array.

push adds at the end and swaps upwards at most log n times, so O(log n). pop moves the last item to the root and sifts it down.

Save yourself the pain

Common mistakes

Oops

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

Do this instead

Sorting is O(n log n). A size-K heap does it in O(n log k), and k is tiny.

Oops

Thinking a heap's array is fully sorted.

Do this instead

Only the root is guaranteed. The rest is just 'each parent beats its children'.

Your mission

Build your own heap

~45 min

Quick check

You find the K largest of n numbers with a min-heap capped at size K. What's the time complexity?

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.