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

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.