I understand that in Heaps we add them from left to right. I understand how to add and delete. But why is it from left to right, is there something that prevents it from being right to left or something like that. My intuition tells me that it has something to do with the index.
1
-
$\begingroup$ Left/right are in fact irrelevant concepts here. What matters is that the element $i$ has chilren $2i+1$ and $2i+2$. You could alternate the order in the successive levels, at the expense of a complicated formula and much fuss. $\endgroup$– user16034Commented Jul 18, 2022 at 14:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If you are referring to the binary heap, then you are right that it has something to do with the index. The left child of a node is at index $2*i$ while the right child is $2*i+1$, where $i > 0$ is the index of the parent in the array representation of the binary heap. Since a new element is added at the smallest empty index in the array, this element will be a left child when its parent has no children.
