A binary heap is stored in a plain array, filled level by level from the left. With 0-based indices the node at i has
\mathrm{left}(i) = 2i + 1, \qquad \mathrm{right}(i) = 2i + 2, \qquad \mathrm{parent}(i) = \left\lfloor \frac{i - 1}{2} \right\rfloor
Write heap_indices(size, i) returning the triple (parent, left, right) for a heap of size items, with -1 wherever the node does not exist: the root has no parent, and a child beyond the end of the array is missing.
Examples
Input: size = 7, i = 1
Output: (0, 3, 4)
Input: size = 5, i = 2
Output: (0, -1, -1)
Explanation: indices 5 and 6 are past the end of a five-item heap.
Constraints
1 <= size <= 10**9,0 <= i < size
Goals
- Navigate a binary heap with arithmetic instead of pointers
- Treat an index outside the array as a missing child or parent
- See why a heap needs no node objects at all