Welcome to Programming and Data Structures

Although we think of the heap as a tree structure, and might implement it in a method similar to a linked list using nodes and pointers, heaps are most commonly implemented using arrays.

Because heaps are complete binary trees, they have a very regular structure that makes them easy to pack into an array. We know that the first level has 1 node, the second level has 2 nodes, the third level has up to 4 nodes, and so on.

This nature, combined with the fact that we know any gaps must be at the end of the last level, means that we can represent the heap in an array without any wasted space. We simply store the nodes in the array in level order, filling in each level from left to right before moving to the next level.

For example, consider the node holding 8 in our sample heap. It is located at index 1 in the array. Its parent is at index \(floor((1 - 1) / 2) = 0\text{,}\) which holds 20. Its left child is at index \(2 * 1 + 1 = 3\text{,}\) which holds 3, and its right child is at index \(2 * 1 + 2 = 4\text{,}\) which holds 4.

There are some special cases. The root node at index 0 has no parent. And not every node has two children; if a node is at or near the bottom of the heap, it may have one child or no children at all. We need to check that the calculated child indices are less than the number of values in the heap before trying to access them.

For example, in our sample heap, the node holding 12 is at index 2. Its left child would be at index \(2 * 2 + 1 = 5\text{,}\) which holds 6, but its right child would be at index \(2 * 2 + 2 = 6\text{.}\) Since our heap only has 6 elements, it uses indices 0 through 5. That means index 6 is out of bounds, indicating that the node holding 12 has no right child. Similarly, if we start from the node containing 5 at index 5, we find that its left child would be at index \(2 * 5 + 1 = 11\) and its right child at index \(2 * 5 + 2 = 12\text{.}\) Both indices are out of bounds, indicating that the node holding 6 has no children.