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.

  • 1
    $\begingroup$ The answer depends on the order in which you store the nodes. $\endgroup$ – Yuval Filmus Jun 21 '19 at 18:43

Let's assume you store the nodes by level and then from left to right. Here are the first few levels:

  1. Root: $1$
  2. Children of root: $2,\ldots,k+1$
  3. Grandchildren of root: Children of $2$: $k+2,\ldots,2k+1$; Children of $3$: $2k+2,\ldots,3k+1$, ...

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...

  • 1
    $\begingroup$ Thank you, this worked out for me, also, thanks for the explanation. I did prove it with induction and it seems to work :). $\endgroup$ – user106782 Jun 24 '19 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy