How it works
A complete binary tree stores in an array with no gaps, so parent and child indices are computed arithmetically rather than stored.
Use index arithmetic to move between parent and children without references.
Common error
Applying the arithmetic to a tree that is not complete, where the mapping breaks.
Worked example
Example
Zero-based index i
Left child: 2*i + 1
Right child: 2*i + 2
Parent for i > 0: (i - 1) / 2 using integer divisionThe complete-tree shape lets an array encode the links. A calculated child index is valid only if it is smaller than the current heap size.
Exercises
7.2.1 · Explain
For index 3 in a zero-based heap, give the parent and possible child indices.
Show solution
The parent is index 1. Child indices are 7 and 8, provided those positions exist.
7.2.2 · Write code
For a heap of size 6, print the existing child indices of node 2.
Show solution
Check computed positions against the heap size.
One valid solution
int size = 6, i = 2;
int left = 2*i+1, right = 2*i+2;
if (left < size) System.out.println(left);
if (right < size) System.out.println(right);Expected output
5