The Gateway to Computer Science Excellence
0 votes
92 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[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[d2 + d + 1] and so on. What index does maps the jth child for (1 ≤ j ≤ d) of the  ith index node?

in DS by Junior (835 points)
edited by | 92 views
+1

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

0
Pls elaborate
0

What index does maps the jth child for (1 ≤ j ≤ d) of ith index node?

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

+1

@syncronizing

Answered as per your requirement

2 Answers

+3 votes
Best answer

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

by Boss (23.5k points)
selected by
+1 vote

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

by Veteran (65.8k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,394 answers
198,594 comments
105,446 users