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

Dark Mode

406 views

2 votes

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 ≤* j *≤ *d)* of the **i**^{th} index node?

1

0

4 votes

Best answer

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

1 vote

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