A complete, or almost complete, binary tree fills every level except possibly the last. The final level is packed from left to right, so the tree has no gaps. This structure appears in binary heaps, where it provides the shape needed to keep the highest-priority element at the root. section 10.10 section 10.22
Use level-order, zero-based indexes to represent the tree in an array:
- Store the root at index 0 and visit nodes from top to bottom, moving left to right within each level. section 10.15
- For a node at index i greater than 0, find its parent at integer division (i - 1) / 2. section 10.15
- Find the left and right children of index i at 2i + 1 and 2i + 2. section 10.15
- Rely on left justification to keep the array compact, without holes between the first and last elements. section 10.15
Restoring the shape after removing the root
Removing the root directly would leave two subtrees without a common root. Instead, move the last array element to index 0. This restores the complete-tree shape immediately; a heap implementation can then push the replacement downward to restore priority ordering. section 10.18
Use the figure to trace level-order indexes and see why a complete binary tree maps directly onto an array. section 10.15
