Heap

A min-heap is a tree where every parent is no bigger than its children, so the smallest value is always at the top. It is stored as a plain array.

An empty min-heap

A min-heap keeps the smallest value at the top: every parent is ≤ its children. It is stored as a plain array — children of i sit at 2i+1 and 2i+2.

Step 1 / 28
Size
0
Swaps
0

Step by step

The example above, written out — the same steps the animation plays.

  1. 1An empty min-heap. A min-heap keeps the smallest value at the top: every parent is ≤ its children. It is stored as a plain array — children of i sit at 2i+1 and 2i+2.
  2. 2Insert 7. 7 goes in the next free spot (the end of the array).
  3. 3Insert 3. 3 goes in the next free spot (the end of the array).
  4. 43 vs parent 7. 3 < 7: swap up.
  5. 5Sift up. 3 moves up a level.
  6. 6Insert 9. 9 goes in the next free spot (the end of the array).
  7. 79 vs parent 3. 9 ≥ 3: heap order holds — stop.
  8. 8Insert 1. 1 goes in the next free spot (the end of the array).
  9. 91 vs parent 7. 1 < 7: swap up.
  10. 10Sift up. 1 moves up a level.
  11. 111 vs parent 3. 1 < 3: swap up.
  12. 12Sift up. 1 moves up a level.
  13. 13Insert 5. 5 goes in the next free spot (the end of the array).
  14. 145 vs parent 3. 5 ≥ 3: heap order holds — stop.

…and 14 more steps — press Play above to watch them all.

What's happening?

  1. Insert adds the value at the end, then swaps it up while it is smaller than its parent.
  2. Extract-min takes the top, moves the last value to the top, then swaps it down with its smaller child.
  3. The children of position i live at 2i+1 and 2i+2 — no pointers needed.

Complexity

Time
O(log n) insert and extract-min · O(1) to look at the minimum
Space
O(n)

Where you'll meet it

Priority queues: task schedulers, Dijkstra's shortest path, "top K" problems, merging sorted streams, and heap sort.

Common mistake

Expecting the array to be sorted. A heap only guarantees each parent ≤ its children — siblings can be in any order.

FAQ

Heap vs binary search tree?

A heap only knows where the smallest value is; a BST keeps everything in order. Heaps are simpler and faster for "give me the minimum".

Why store a tree in an array?

A heap is always a complete tree, so positions map neatly to indexes — it is compact and cache-friendly.

What is a max-heap?

The same with the order flipped: the largest value is at the top.