What Is a Heap?
A Heap is a complete binary tree kept so the minimum (or maximum) is always quick to remove. It's the standard implementation of a priority queue, used wherever you must repeatedly pull "the most urgent next item" — Dijkstra's shortest paths, Huffman coding, job scheduling.
The one-line idea: "don't sort everything; just maintain the one extreme in O(log n)." When you don't need a full sort (O(n log n)), a heap is far cheaper.
A Complete Binary Tree in an Array
A heap is usually one array. For index i:
- •left child =
2i + 1, right child =2i + 2, parent =(i - 1) / 2
A min-heap always satisfies "parent ≤ both children" (a max-heap is the opposite), so the root holds the minimum. Note siblings are not ordered — a heap keeps only the parent–child relation, not a full sort.
Two Core Operations
Insert (push): put the new value at the end of the array, then while it's smaller than its parent, swap it upward (sift-up) until it finds its place.
Delete (pop): return the root (the min), move the last element to the root, then swap it downward with its smaller child (sift-down) until the heap property is restored.
Both move only along the tree height, so each is O(log n).
How It Works
Step 1. push: append at the end → compare with parent → swap if it violates the rule (sift-up) → repeat to the root or until it stops.
Step 2. peek: reading the root (arr[0]) gives the minimum in O(1).
Step 3. pop: swap root with the last and remove the last → compare the new root with its smaller child → swap if violated (sift-down) → repeat to a leaf or until it stops.
The AlgoNote visualization colors which nodes are compared and swapped during sift-up and sift-down, step by step.
Time and Space Complexity
| Operation | Complexity |
|---|---|
| Insert / delete | O(log n) |
| Peek min | O(1) |
| Build heap | O(n) |
| Space | O(n) |
Walking Through an Example
Insert 5, 3, 8, 1 into a min-heap one by one.
- •insert 5 → [5]
- •insert 3 → smaller than parent 5, bubbles up → [3, 5]
- •insert 8 → larger than parent 3, stays → [3, 5, 8]
- •insert 1 → smaller than 5 then smaller than 3, bubbles up → [1, 3, 8, 5]
Now a pop returns the minimum 1 first.
Common Mistakes
- •Mistaking it for a full sort: printing the heap array is not sorted output (siblings aren't ordered).
- •Min vs max: a single comparison direction flips min-heap ↔ max-heap.
- •Arbitrary deletion: without knowing the position, finding it costs O(n). Known position → sift in place in O(log n).
See It in Action on AlgoNote
Watch a value bubble up on insert (sift-up) and the root sink down on removal (sift-down), step by step on AlgoNote.