Heap tree as an array

A heap is a complete binary tree, but the Heap class stores no nodes or pointers, just an array. Number the nodes level by level, left to right, and node number i goes in arr[i]. The dashed arrows show where each node lands.

From the index alone, three formulas find a node's family (Java's integer division drops the fraction):

• getLeftChild(i) = 2i + 1: the left child of index 1 is 1·2 + 1 = 3
• getRightChild(i) = 2i + 2: the right child of index 1 is 1·2 + 2 = 4
• getParent(i) = (i − 1) / 2: the parent of index 4 is 3 / 2 = 1, and of index 3 is 2 / 2 = 1 too

A child index of currSize or more doesn't exist (childExists is false), and the root, index 0, has no parent. Click any node or cell to see its parent and children.