Log In
1 vote

A $d-$ary heap is a binary heap, but instead of $2$ children, nodes have $d$ children. A $d-ary$ heap can be represented by $1-D$ array as follows. The root is kept in $A[1]$, and it’s $d$ children are kept in order in $A[2]$ through $A[d+1]$ , their children are kept in order in $A\left [ d+2 \right ]$ through $A\left [ d^{2}+d+2 \right ]$ and so on.What index does map the $j-th$ child for $\left ( 1\leq j\leq d \right )$ of $ith$ index node?

$A)d\left ( i-1 \right )+1$

$B)d\left ( i-1 \right )+j+1$ 

Someone explain it. I felt difficulty in solving it, because of this equation $A\left [ d^{2}+d+2 \right ]$

in DS
edited by
since,  A[1] is root node and its total d children are from A[2] to A[d+1]..
Now A[2] have d children from A[(d+2)]  to A[(d+2)+d]

A[3] have d children from A[(d+2)+d+1] to A[(d+2)+d+d]..

now observe,  we are adding d to each node from A[2] to  A[d+1] i. e. total d nodes..
So,  if last children of node A[2] have index A[(d+2)+d],
then last children of node A[3] have index A[(d+2)+2d]

Similary last children of A[d+1] will have index A[(d+2) + d*d]
because there are d nodes from A[2] to A[d+1] and each has d children, so we are adding d nodes d times...
To solve this question, take some small values of d and check the options..


$A\left [ 2 \right ]$ to $A\left [ d+1 \right ]$ there are $d$ children.

Now, $A\left [ d+2 \right ]$ to $A\left [d^{2}+ d+2 \right ]$, there are how many children each?

if we divide $A\left [d^{2}+ d+2 \right ]$ it will be $A\left [(d( d+1)+1)+1 \right ]$

That means $(d+1)$ node has $d$ child each and $2$. extra node. why??

not getting this logic :(

1 Answer

0 votes

Ans is B.

say we have a 3-ary heap so value of d=3, now say our tree is like--> 

So our array will be like

Now say we want to find the location of 3rd child of the 1st node.. So j=3 and i=1

Putting the value the value of i,d,j in eqn A we get 0, so that is Wrong

But putting the values in eqn B we get 4, so eqn B is Correct.

Related questions

6 votes
4 answers
Consider a hash table with $N$ slots. It is given that the collision resolution technique used in chaining. Assume simple uniform hashing, what is the probability that the last $k$ slots are unfilled after the first $’r’$ insertions? $A)\left ( 1-\frac{N}{k} \right )^{r}$ $B)\left ( 1-\frac{k}{N} \right )^{r}$ $C)\left ( 1+\frac{N}{k} \right )^{r-1}$ $D)\left ( 1-\frac{k}{N} \right )^{r-1}$
asked May 5, 2019 in DS srestha 607 views
0 votes
1 answer
Consider the following function foobar(), which takes binary tree as input. int foobar(struct node *root){ if(!root) return 0; if((!root->left)&&(!root->right)) return 10; else{ int i=foobar(root->left); int j=foobar(root->right); return i+j; } } What does the above ... tree. $B)$ Number of leaves in binary tree $C)$ Sum of leaves node of binary tree. $D)$ None What return $10$ actually means?
asked May 4, 2019 in DS srestha 143 views
1 vote
2 answers
Consider a single array $A\left [ 0...........(n-1) \right ]$ is used to implement two stacks. Two stacks grows from opposite end of the array. Variable $top_{1}$ and $top_{2}$ points to the location of the topmost elements in each of the stacks with initial values of ... represents the number of elements are present in the array at any time? $A)n-top_{2}+top_{1}$ $B)n+1-top_{2}+top_{1}$
asked Apr 26, 2019 in DS srestha 185 views
0 votes
1 answer
I want longest path from root to leaf. Then which code is correct among Code-1 or Code-2? Code-1) int tree(Struct node *root){ int a=0, b=0,c=0; if(root==NULL) return 0; if((root->left==NULL)&&(root->right==NULL)) return 1; a=1+tree(root->left); b=1+tree(root->right); c= ... 0; if((root->left==NULL)&&(root->right==NULL)) return 1; a=tree(root->left); b=tree(root->right); c=1+max(a,b); return c; }
asked Apr 22, 2019 in DS srestha 131 views