Questions
12 of 26
How is a Heap implemented using an Array? (Parent/Child index math)
Difficulty: 3/10
Array Representation of Heap
Because a heap is complete, it can be stored compactly in an array without explicit child pointers. For zero-based indexing, the parent of index i is (i-1)/2, the left child is 2i+1, and the right child is 2i+2. This representation provides excellent cache locality and avoids pointer overhead.
javascript
- 1
Zero-based arrays are most commonly used.
- 2
No null slots are required for missing children.
- 3
The complete-tree property guarantees compact storage.
- 4
Heap operations rearrange array elements using swaps.
Follow-up Questions
- How do the formulas change for one-based indexing?
- Why does array representation work especially well for heaps?