Heap (Priority Queue)
Medium+90 XPA tree that always keeps the smallest (or largest) on top — and secretly lives in a plain array.
No visualization loaded.
Watch
—
Press Run to begin.
A heap is a special tree with one simple promise: the smallest value is always sitting right on top (that's a 'min-heap'; flip it and the biggest is on top — a 'max-heap'). The magic trick is that this tree doesn't need real branches and pointers — it lives inside an ordinary array. The top of the tree is slot 0, and for any slot i, its two children are at slots 2i+1 and 2i+2. So the tree shape and the array are the SAME thing, just drawn two ways.
▸Why would I use a heap instead of just sorting?
When you only ever need the smallest (or biggest) thing right now, again and again — like 'serve the most urgent task next.' Sorting the whole list every time is wasteful. A heap gives you the top item instantly and re-settles itself in one quick climb, so repeatedly grabbing the best is fast.
▸How can a tree live inside an array?
By a counting rule, not pointers. Put the root at index 0. Its children go at 1 and 2. Their children at 3,4,5,6. In general, the children of index i are at 2i+1 and 2i+2, and a node's parent is at (i−1)÷2 rounded down. Follow that rule and the flat array IS the tree — no extra memory for links.
▸What's 'sift up' / 'bubble up'?
When you add a value, you drop it at the end of the array (the bottom of the tree), then let it climb: keep swapping it with its parent as long as it's smaller. It stops when its parent is smaller-or-equal. A handful of swaps — at most the height of the tree — fixes the whole heap.
▸Why is each insert O(log n)?
Because the tree is short and bushy: doubling the items only adds one more level. A new value climbs at most one level per swap, so the work is the height of the tree — about log n swaps — not a full pass over everything.
▸Is a heap fully sorted?
No — and that's the point. A heap only guarantees the TOP is the min (or max). Brothers and cousins can be in any order. That looser promise is cheaper to maintain than full sorting, which is exactly why grabbing 'the next best' is so fast.
How the work grows
O(log n) per insert / remove-top is excellent — barely grows. The tree's height is about log n, and an item only ever climbs (or sinks) one level per swap, so each insert or remove touches at most log n slots — barely grows as the heap gets huge. Space is just the array holding the items.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.