Consider an array representation of an n element binary heap where the…

Concept: In the level-order (1-indexed) array representation of a complete binary tree used for a binary heap, a node stored at index k has its two children stored at indices 2k and 2k+1. This fixed arithmetic relationship between an index and its children is what lets the parent of any node be recovered directly from its own index, without following any pointers.

Application:

1. By the definition above, for a node at index k, its left child is at index 2k and its right child is at index 2k+1.

2. To recover the parent of a node at index i, invert this relation. If i is even, i = 2k, so k = i/2 exactly. If i is odd, i = 2k+1, so k = (i-1)/2, which is the same value as floor(i/2).

3. Both the even and odd cases collapse into a single closed-form expression: parent(i) = floor(i/2), valid for every i from 2 to n (index 1 is the root and has no parent).

Cross-check: Verify directly against the array layout: nodes 2 and 3 are both children of node 1, and floor(2/2) = 1 and floor(3/2) = 1 — both give the same parent. Nodes 4 and 5 are both children of node 2, and floor(4/2) = 2 and floor(5/2) = 2 — again the same parent. Every sibling pair (2k, 2k+1) maps back to the same parent k under this formula, confirming it is internally consistent across the whole array.

So the parent of the element at index i is floor (i/2).