level 6 · Trees
Heap & Priority Queue
A tree that always keeps the biggest thing on top, ready to grab.
what is it
Start here
A heap is a binary tree with one strict rule: every parent is bigger than its children. It doesn't care about left-versus-right like a search tree — it only cares up and down. The consequence is simple and powerful: the biggest value in the whole structure is always sitting at the very top.
That makes a heap the natural way to build a priority queue — a line where the most important item is always served next, no matter when it arrived. Hospital triage, task schedulers, and Dijkstra's shortest-path algorithm all lean on exactly this.
Watch an insert. The new value goes in at the bottom, then it climbs: it compares itself to its parent and, if it's bigger, they swap. It keeps climbing until it meets a parent that's bigger than it, or reaches the top. That climb is called sift-up, and it only ever touches one path from the leaf to the root — about log n steps.
Because the tree is always kept complete (filled left to right, no gaps), a heap is usually stored as a plain array with no pointers at all: a node at index i finds its children at 2i+1 and 2i+2. The tree you see is really just that array, drawn.
real-life analogy
Picture it
Imagine a knockout bracket where the winner always rises. When a new player joins at the bottom, they challenge the player above them; if they win, they move up and challenge again. They keep rising until they meet someone stronger. The overall champion always ends up at the very top — that's the max at the root of a heap.
interactive visualization
Watch it run
Each value is added at the bottom, then climbs to its rightful level.
A heap is a binary tree with one rule: every parent is bigger than its children (a max-heap). That means the biggest value is always sitting right at the top, ready to grab.
step 01/22
- comparing
- moving
- target · placed
- on the path
space · play ← → · step
| 1 | function insert(heap, value) { |
| 2 | heap.push(value); |
| 3 | let i = heap.length - 1; |
| 4 | while (i > 0) { |
| 5 | const parent = (i - 1) >> 1; |
| 6 | if (heap[parent] >= heap[i]) break; |
| 7 | swap(heap, i, parent); |
| 8 | i = parent; |
| 9 | } |
| 10 | } |
variables right now
Nothing in play yet — press play.
the dry run · every step, in words
22 stepscomplexity
What it costs
- best case
- O(1)
- average
- O(log n)
- worst case
- O(log n)
- extra memory
- O(n)
Inserting sifts up one path from leaf to root — O(log n). Peeking at the maximum is O(1), because it's always the root. Removing the max is O(log n) too. That log-n cost for always knowing the top is what makes a heap the go-to priority queue.
- O(1)
- O(log n) · this one
- O(n)
- O(n log n)
- O(n²)
common mistakes
Common traps
Expecting a heap to be fully sorted.
It isn't. A heap only guarantees the max (or min) is on top. The rest is loosely ordered — enough to find the top fast, but not a sorted list.
Confusing a heap with a binary search tree.
A BST orders left-vs-right by value so you can search. A heap orders parent-vs-child so the extreme is on top. You can't binary-search a heap.
Sifting the new value down instead of up.
A freshly inserted value goes in at the bottom and climbs up toward the root. Sifting down is for removal, when you drop the last value into the empty top.
quiz
Check yourself
Three questions. Get them all right to finish the lesson.
+90 XP01In a max-heap, where is the largest value always found?
02You insert a new value into a heap. What happens?
03What is a heap most commonly used to build?
practice
Solve it on LeetCode
You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.