How does a heap work?

Every heap operation follows the same plan. First make the change at the one place that keeps the tree complete: the end of the array. Then repair the order rule along a single path between the root and a leaf. A complete tree with n nodes is only about log₂ n levels tall, so that repair costs O(log n).

push: add at the end, then sift up

Put the new value at the end of the array — the next free spot on the bottom level. The tree is still complete.
Compare it with its parent. If it's smaller, swap them: it rises one level. Repeat until its parent is smaller or equal, or it reaches the root.

Only the new value's path to the root can break the order rule, and every swap moves a smaller value up past a bigger one — so each swap fixes the order where it happens, and nothing else has to move.

Pushing 3 into the min-heap 1, 4, 2, 7, 5, 6, 8. Frame 1: 3 goes at the end, index 7, under 7. Frame 2: 3 is smaller than its parent 7, so they swap; the array reads 1, 4, 2, 3, 5, 6, 8, 7. Frame 3: 3 is smaller than its new parent 4, so they swap; the array reads 1, 3, 2, 4, 5, 6, 8, 7. Frame 4: its parent is now 1, which is smaller, so it stops. The heap is valid again after two swaps. — Sift up: the new value climbs while it is smaller than its parent.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 7 more sections, 1 drawing, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

pop: move the last value to the top, then sift down
peek: read index 0
Why O(log n)?
The whole min-heap
A max-heap is the same code, flipped
Building a heap from n values
Key takeaways

Prev Next

Mark completed

Was this helpful?

How does a heap work?

push: add at the end, then sift up

Keep reading. It's free.

Keep exploring