HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Why does the formula floor((i-1)/2) find the parent node in a binary heap?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whythenodeparentheapbinarydoesfindformulafloor

Problem

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with
parent index = floor((i-1)/2)

I have tried to explain why it works. Can anyone help me verify this?

Took reference from Why does the formula 2n + 1 find the child node in a binary heap? thanks to @Giulio

Solution

Levels by levels, the indexes of a binary heap are

$$0\\1\ \ \ \ \ \ \ \ \ \ \ \ \ 2\\3\ \ \ \ \ \ 4\ \ \ \ \ \ 5\ \ \ \ \ \ 6\\7\ 8\ 9\ 10\,11\,12\,13\,14\\\cdots$$

and it is rather clear that the sons of $n$ are $2n+1$ and $2n+2$.

By inversion, the father of $m$ is one of $\dfrac{m-1}2$ or $\dfrac{m-2}2$, and more precisely the one that is an integer.

Context

StackExchange Computer Science Q#130167, answer score: 2

Revisions (0)

No revisions yet.