Question

A d-ary heap is like a binary heap, but instead of two children, nodes have 'd' children. A d-ary heap can be represented in a 1-dimensional array as follows. The root is kept in A[1], its d children are kept in order in A[2] through A[d + 1] their children are kept in order in A[d + 2] through $A[d^2+d+1]$ and so on. What index does maps the $j^{th}$ child for $(1\le J\le d)$ of $i^{th}$ index node?

• A. $d(i-1)+j+1$
• B. $(d\times i)+j+1$
• C. $d(i-1)+1$
• D. $d(i-1)+j$

Answer 1

The correct option is A $d(i-1)+j+1$

Consider 3 array heap:


So, root at at A[1] i.e., d(i -1) + j + 1
= 3(1 - 1) + j +1
=0 + 0 + 1 =1
$1^{st}childofroot=d(i-1)+j+1$
= 3(1 - 1) + 1 + 1 = 2
$3^{rd}childofroot=d(i-1)+j+1$
= 3(1 - 1) + 3 + 1
= 0 + 4 = 4
Index for node 7 = d(i -1) + j + 1
3(2 - 1) + 3 + 1
= 3 + 3 + 1 = 7
So, index maps to d(i - 1) + j + 1.