Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?
All questions regarding my problem I found talk about binary heaps, I just can’t think of a simple solution.
Let's assume you store the nodes by level and then from left to right. Here are the first few levels:
Let us guess that just like in the binary case, the formula for the leftmost child of $v$ is of the form $\alpha v + \beta$.
If we consider two adjacent nodes at the same level, their leftmost children will differ by $k$ (for example, leftmost child of $2$ is $k+2$, whereas leftmost child of $3$ is $2k+2$), hence $\alpha = k$.
We can find $\beta$ by considering the root: $k \cdot 1 + \beta = 2$ implies that $\beta = -(k-2)$. Overall, we get $$ kv-(k-2) = k(v-1) + 2. $$ This works for the root by construction. When $v = 2$, we get $k (2-1) + 2 = k+2$, which also works out. My guess it that this formula works out, and you should be able to prove it by induction. That's where you come in...
