gotchaMinor
Why does the formula floor((i-1)/2) find the parent node in a binary heap?
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
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.
$$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.