edited by
470 views
1 votes
1 votes

A $d-$ary heap is a binary heap, but instead of $2$ children, nodes have $d$ children. A $d-ary$ heap can be represented by $1-D$ array as follows. The root is kept in $A[1]$, and it’s $d$ children are kept in order in $A[2]$ through $A[d+1]$ , their children are kept in order in $A\left [ d+2 \right ]$ through $A\left [ d^{2}+d+2 \right ]$ and so on.What index does map the $j-th$ child for $\left ( 1\leq j\leq d \right )$ of $ith$ index node?

$A)d\left ( i-1 \right )+1$

$B)d\left ( i-1 \right )+j+1$ 


Someone explain it. I felt difficulty in solving it, because of this equation $A\left [ d^{2}+d+2 \right ]$

edited by

1 Answer

0 votes
0 votes

Ans is B.

say we have a 3-ary heap so value of d=3, now say our tree is like--> 

So our array will be like

Now say we want to find the location of 3rd child of the 1st node.. So j=3 and i=1

Putting the value the value of i,d,j in eqn A we get 0, so that is Wrong

But putting the values in eqn B we get 4, so eqn B is Correct.

Related questions

0 votes
0 votes
1 answer
2