1
$\begingroup$

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.

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

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

$\endgroup$
  • 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$ – Marcel B Jun 24 at 20:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.