Math for coding interviews/Array indexing for trees
Heap Array Indexing: The 2i+1 and 2i+2 Formulas
A heap looks like a tree but is actually stored as a flat array. The math that makes this work: if a node is at index i, its left child is at index 2i+1, its right child is at index 2i+2, and its parent is at index (i-1)/2 (rounded down). These simple formulas replace the need for actual pointers.
See it for yourself
The tree visualization on the left, the array on the right. Click a node in the tree and the corresponding array index highlights. Move to a child - see the 2i+1 formula compute live.
Array indexing for trees
A heap looks like a tree but is actually stored as a flat array. The math that makes this work: if a node is at index i, its left child is at index 2i+1, its right child is at index 2i+2, and its parent is at index (i-1)/2 (rounded down). These simple formulas replace the need for actual pointers.
Think of it this way: A tournament bracket stored as a list. The champion is position 1. Their two finalists are positions 2 and 3. The semi-finalists are positions 4, 5, 6, 7. Each level doubles.
For algorithms: Because a heap is a complete binary tree, its height is always log(n). Bubble-up and sink-down operations travel at most log(n) steps, giving O(log n) insert and extract.
Real-world analogy
A tournament bracket stored as a list. The champion is position 1. Their two finalists are positions 2 and 3. The semi-finalists are positions 4, 5, 6, 7. Each level doubles.
Why it matters in interviews
Because a heap is a complete binary tree, its height is always log(n). Bubble-up and sink-down operations travel at most log(n) steps, giving O(log n) insert and extract.