Made Easy Test Series: DS

Question

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 ]$

Comments

since,  A[1] is root node and its total d children are from A[2] to A[d+1]..
Now A[2] have d children from A[(d+2)]  to A[(d+2)+d]

A[3] have d children from A[(d+2)+d+1] to A[(d+2)+d+d]..

now observe,  we are adding d to each node from A[2] to  A[d+1] i. e. total d nodes..
So,  if last children of node A[2] have index A[(d+2)+d],
then last children of node A[3] have index A[(d+2)+2d]

Similary last children of A[d+1] will have index A[(d+2) + d*d]
because there are d nodes from A[2] to A[d+1] and each has d children, so we are adding d nodes d times...
To solve this question, take some small values of d and check the options..

---

@ankitgupta.1729

$A\left [ 2 \right ]$ to $A\left [ d+1 \right ]$ there are $d$ children.

Now, $A\left [ d+2 \right ]$ to $A\left [d^{2}+ d+2 \right ]$, there are how many children each?

if we divide $A\left [d^{2}+ d+2 \right ]$ it will be $A\left [(d( d+1)+1)+1 \right ]$

That means $(d+1)$ node has $d$ child each and $2$. extra node. why??

not getting this logic :(

---

I think it has to be A[ d^2 + d + 1 ] instead of A[ d^2 + d + 2 ].

Answer 1

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.