406 views

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, its d children are kept in order in A through A[d + 1] their children are kept in order in A[d + 2] through A[d2 + d + 1] and so on. What index does maps the jth child for (1 ≤ j ≤ d) of the  ith index node?

Jth 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 jth child for (1 ≤ j ≤ d) of ith index node?

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

@syncronizing

Here we are given d-ary..

We need to find the jth child of ith node.

Before coming to the 1st child of the ith 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 is at index : 1+d

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

Last child of A 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 jth child of the ith node. So simply add j it becomes d(i-1) + j + 1

given that it is a heap tree, therefore when your talking about ith 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 ith 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 jth child of ith node ===> ( ( i - 1 ) * d + 1 ) + j

1
2,924 views