The heap denotes an ordered binary tree. A heap can be built from a one-dimensional array. In this one-dimensional array:

• n represents the index of the parent node (n = 1, 2, 3, …)
• 2n represents the index of the left child
• 2n + 1 represents the index of the right child

If we have the following array, we can construct a heap from it following the rules outlined above.

Since there are 6 elements, the heap will have 6 nodes. Although the indices of the array start at 0, when numbering the elements in the heap, the first element starts at 1. We’ll follow the formula to construct the heap. The root node is located at n = 1, which in this case is 7.

The children of 7 are located at 2n and 2n+1. Since the root node is at n = 1, the left child is located at 2 • 1 = 2, and the right child is located at
(2 • 1) + 1 = 3. The left child is 2 and the right child is 9.

The heap is built from left to right. The next elements to be added are the left and right children of 2. The node with the value of 2 is located at n = 2. The left child is located at 2 • 2 = 4, and the right child is located at (2 • 2) + 1 = 5. The left child is 4 and the right child is 5.

The last element that needs to be added is under number 9; this will be the left child of number 9. Number 9 is located at node 3. The left child of node 3 is located at 2n = 2 • 3 = 6. The value at n = 6 is 3. The heap is constructed from the array.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this data structure and many more.