Are the equations of right and left children of heap accurate?

Question

In the heap data structure, do the two equations

left = 2i+1
right = 2i+2

apply on any given heap? if not, in what condition they shall be efficient?

Answer 1

According to D.S. Malik "A heap is a list in which each element contains a key, such that the key in the element at position k in the list is at least as large as the key in the element at position 2k + 1 (if it exists) and 2k + 2 (if it exists)."

You should also note the element's position in the list: "in general, for the node k,which is the k-1th element of the list, its left child is the 2kth (if it exists) element of the list, which is at position 2k-1 in the list, and the right child is the 2k + 1st (if it exists) element of the list, which is at position 2k in the list."

When studying I found it helpful to actually input some indexes and make sure you get the element you were hoping. Best of luck.

Answer 2

It depends on where the root is. If the root is at index 0 in the array, then your equations are correct. The left node is at index 2i + 1 and the right node is at index 2i + 2.

Many examples have the root at index 1 in the array. In that case, the left child is at index 2i, and the right node is at index 2i + 1.