Test-series

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² + d + 1] and so on. What index does maps the j^th child for (1 ≤ j ≤ d) of the  i^th index node?

Comments

J^th node childs lie at the index

( j - 1 ) * d + 2  ----------------- to -------------- ( j - 1 ) * d + 2 + ( d - 1 )

which is equivalent to

( j - 1 ) * d + 2  ----------------- to -------------- ( j ) * d + 1

---

Pls elaborate

---

What index does maps the j^th child for (1 ≤ j ≤ d) of i^th index node?

Edit your question..it is missing this vital parameter.. 
 

---

@syncronizing

Answered as per your requirement

Answer 1

Here we are given d-ary..

We need to find the j^th child of i^th node.

Before coming to the 1st child of the i^th node, all the nodes starting from root to the last child of (i-1)^th node has to be covered.

Indexing starts from 1.

Last child of A[1] is at index : 1+d

Last child of A[2] is at index  : (1+d) + d =1 +2d

Last child of A[3] is at index : ((1+d) + d) + d  =1 + 3d

Last child of A[k] is at index : (1+d) + (k-1)d =d+1+kd-d= 1 +kd

So, last child of A[i-1] is at index : 1+ (i-1)d

We have reached the last child of the (i-1)^th node.

Now we need to find j^th child of the i^th node. So simply add j it becomes d(i-1) + j + 1

Answer 2

given that it is a heap tree, therefore when your talking about i^th children's that means all the other nodes which index less than i are fully extended.

how many such nodes are there?

1,2,3,4,5,6...,i-1 ===> total i-1 nodes are fully extended ===> (i-1) * d

Note that we count children's of some nodes but not the root ===> total nodes completed before going Jth children's = ( i - 1 ) * d + 1

therefore i^th node children's starts from ( ( i - 1 ) * d + 1 ) + 1  ----- to ----- ( ( i - 1 ) * d + 1 ) + ( d )

which is simplified as  ( ( i - 1 ) * d + 2 ) ----- to ----- (  i  * d + 1 )

 

if you want j^th child of i^th node ===> ( ( i - 1 ) * d + 1 ) + j