Binary Heap Visualization for Coding Interviews
Sift-up (insert) + sift-down (extract-min); array-backed.
Concept
A binary heap is a complete binary tree stored implicitly in an array, where every node satisfies a heap ordering against its children - in a min-heap, every parent is no larger than either child; in a max-heap, every parent is no smaller. The completeness property means the tree fills in level by level, left to right, which lets you skip pointers entirely: for a node at index i, the children live at 2i and 2i+1 and the parent at i/2 (using 1-based indexing). That array layout gives you O(1) random access to any level, O(log n) insert and extract, and an astonishing O(n) bulk heapify that is the foundation of heapsort. The two operations everyone should know cold are siftUp, which restores the heap property after inserting at the end, and siftDown, which restores it after replacing the root with the last element. Binary heaps power priority queues, Dijkstra's shortest paths, A* search, top-k queries, and the scheduled-task execution loop in almost every runtime.
How it works
Insert appends the new element at the first free slot - index size+1 in 1-based indexing - which preserves completeness. That placement almost certainly violates the heap property with the element's parent, so you siftUp: compare with the parent at i/2, swap if the parent is larger (min-heap), and repeat until either the root is reached or the parent is no longer larger. That walk takes at most log n comparisons. ExtractMin returns the root, moves the last element into the root slot, shrinks the array, and siftsDown: compare the new root with its smaller child, swap if the child is smaller, and repeat until both children are no smaller or you fall off the tree. Heapify turns an arbitrary array into a heap in O(n), not O(n log n), by calling siftDown on every non-leaf index from size/2 down to 1. The intuition is that most nodes are near the bottom of the tree and their siftDown cost is O(1); only a handful of near-root calls cost O(log n), and the weighted sum telescopes to linear. Min-heaps and max-heaps differ only in the direction of the comparison in siftUp and siftDown.
Implementation
public class MinHeap {
private int[] data;
private int size;
public MinHeap(int capacity) {
this.data = new int[Math.max(capacity, 16) + 1]; // 1-indexed
this.size = 0;
}
public MinHeap(int[] input) {
this.data = new int[input.length + 1];
System.arraycopy(input, 0, data, 1, input.length);
this.size = input.length;
heapify();
}
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
public int peek() {
if (size == 0) throw new java.util.NoSuchElementException();
return data[1];
}
public void insert(int value) {
if (size + 1 >= data.length) grow();
data[++size] = value;
siftUp(size);
}
public int extractMin() {
if (size == 0) throw new java.util.NoSuchElementException();
int min = data[1];
data[1] = data[size--];
siftDown(1);
return min;
}
/** O(n) bulk heapify by sifting down every internal node. */
private void heapify() {
for (int i = size / 2; i >= 1; i--) siftDown(i);
}
private void siftUp(int i) {
while (i > 1 && data[i / 2] > data[i]) {
swap(i, i / 2);
i /= 2;
}
}
private void siftDown(int i) {
while (2 * i <= size) {
int child = 2 * i;
if (child + 1 <= size && data[child + 1] < data[child]) child++;
if (data[i] <= data[child]) break;
swap(i, child);
i = child;
}
}
private void swap(int i, int j) { int t = data[i]; data[i] = data[j]; data[j] = t; }
private void grow() {
int[] bigger = new int[data.length * 2];
System.arraycopy(data, 0, bigger, 0, data.length);
data = bigger;
}
}Complexity
- Peek:
O(1) - Insert:
O(log n) - ExtractMin:
O(log n) - Heapify:
O(n) - Space:
O(n)
Common pitfalls
- Using 0-based indexing with left=2i+1 and right=2i+2 is fine, but mixing both conventions in the same code base is a bug magnet.
- Calling heapify by inserting each element one at a time - that is O(n log n), not O(n).
- Forgetting to pick the smaller child in siftDown and always descending left, which breaks the heap property on the right subtree.
- Resizing the backing array lazily without handling the case where size exceeds capacity during insert.
- Using Java's PriorityQueue without a comparator when you actually needed a max-heap - the default is a min-heap.
Key design decisions & trade-offs
- Array vs pointer representation — Chosen: Implicit array. No node allocations, parent/child arithmetic is cheap, and cache locality is excellent for the top levels of the heap.
- Heapify strategy — Chosen: SiftDown from size/2 down to 1. Linear-time bulk heapify is strictly faster than n inserts; the proof is a telescoping sum over level heights.
- Binary vs d-ary — Chosen: Binary for simplicity. 4-ary heaps reduce sift height and can win on decrease-key-heavy workloads like Dijkstra, but the code is more complex.
Practice problems
Interview follow-ups
- Extend the heap with decreaseKey in O(log n) using an index map.
- Implement heapsort by repeatedly extracting from a max-heap into the tail of the array.
- Build a top-k filter using a size-k min-heap over a stream.
- Implement a d-ary heap and benchmark it against binary for Dijkstra.
- Build a mergeable heap (binomial or Fibonacci) for applications that need O(log n) meld.
Why it matters
Binary Heap is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".