Array Representation of Binary Heaps
You'll learn how heaps are stored efficiently in arrays using simple index arithmetic to find parents and children.
Why Arrays Work Perfectly for Heaps
Remember that heaps are complete binary trees (filled left-to-right, level-by-level). This predictable structure means we don't need pointers or node objects—we can store everything in a plain array and use math to navigate the tree!
How It Works
Store the heap by reading levels left-to-right, top-to-bottom:
Tree view: Array view:
10 [10, 20, 15, 30, 40]
/ \ 0 1 2 3 4
20 15
/ \
30 40
The root lives at index 0. Every node's position determines where its family members are.
The Magic Formulas
For any node at index i:
- Left child:
2*i + 1 - Right child:
2*i + 2 - Parent:
(i - 1) / 2(integer division)
Example: Node at index 1 (value 20):
- Left child:
2*1 + 1 = 3(value 30) ✓ - Right child:
2*1 + 2 = 4(value 40) ✓ - Parent:
(1 - 1) / 2 = 0(value 10) ✓
Why This Is Brilliant
No wasted space! A complete binary tree with n nodes fits perfectly in an array of size n. You navigate parent-child relationships with arithmetic instead of following pointers—fast and memory-efficient.
Key Takeaway: Binary heaps stored in arrays use index formulas (2*i+1, 2*i+2, (i-1)/2) to navigate the tree structure without pointers, exploiting the complete binary tree property for maximum space efficiency.