How do binary heaps determine their parent if it involves a half (i.e. 1.5)?

Question

I am learning about Binary Heaps and I understand that to get the left child the formula is (2 x index)+1 and to get the right child is (2 x index)+2. That makes sense to me but getting the parent node is where I don't really understand. I know the formula for that is (index - 1) / 2 but how does it work if it returns a half (.5)?

For example, if I am trying to find the parent node of index 3 then that would be (3-1)/2 which gives you 1 so that makes sense but what about index 4? That would be (4-1)/2 which gives you 1.5. So would the parent of index 4 be index 1 or index 2? Looking at a diagram like the one below it makes sense obviously because index 4 is tied to index 1 but from a mathematics standpoint I'm just not sure I understand how to handle it when halves come into play.

Thank you!

Answer 1

It depends on the language in which it is implemented. In some languages / represents an integer division when the operands are integers, which is what you need. For instance, this is the case in Java where 3/2 == 1.

If it is not, then indeed you need to truncate the result to an integer. Python for example, has the integer division operator, //, so that 3//2 == 1.

Alternatively, in many of those languages you can use a shift operator: >>1 corresponds to an integer division by 2.

So here are some equivalent ways to do it when / does not truncate the result to an integer:

// Using bit shift
parentIndex = (childIndex - 1) >> 1
// Using ternary operator based on check whether number is odd
parentIndex = childIndex % 2 > 0 ? (childIndex - 1) / 2 : (childIndex - 2) / 2
// Use remainder of two to get to an even number that can be divided by 2
parentIndex = (childIndex - 2 + childIndex % 2) / 2
// Same thing, but the subtraction of 2 is taken out of the numerator
parentIndex = (childIndex + childIndex % 2) / 2 - 1
// Or doing the explicit truncation
parentIndex = floor((childIndex - 1) / 2)