0

I did anwer the question but I'm not sure if this is right. can you guys double check my answer and let me know if its wrong.

Question 1: For the heap element at position i in the underlying array of a 3-heap, what are the positions of its immediate chidren and its parent? (Give formulas in terms of i.) my Answer1: 2i +1(left child) and 2i+2(right child) and i(parent)

Question 2: For the heap element at position i in the underlying array of a d-heap, what are the positions of its immediate chidren and its parent? (Give formulas in terms of i and d.) my Answer2: di+1(left child) and di+2(right child)

dav
  • 1

2 Answers2

1

Question 1: A 3-heap would have three children. So, the positions of the children of the element at position $i$ would be $3i+1,3i+2,and\,3i+3$. The position of its parent would be $\,floor\left( \frac { (i-1) }{ 3 } \right)$.

Question 2: The positions of the immediate children are $di+1$ through $di+d$. The position of the parent is $\,floor\left( \frac { (i-1) }{ d } \right)$.

acheigrec
  • 11
1

Question 1: A 3-heap would have 3 children and they would be located at the indices (in order) 3i-1, 3i and 3i+1 in a list (assuming the list starts at index 1).

E.g. The list [None, 20, 18, 13, 15, 11, 12, 16, 10, 9, 17] (assuming 20 = index 1) The children to the node 18(index 2) would be 11(index 5), 12(index 6), 16(index 7)

T Williams
  • 11