Advanced data structures and algorithms Question 1 (30 POINTS): Assume we implem

Question

Advanced data structures and algorithms

Question 1 (30 POINTS): Assume we implement heap using s-children per node, rather than two. 1A) (15 POINTS) Extract a formula to compute the index of the parent node for a given node i ie. PARENT(i). Please show your work. 1.B.) (15 POINTS) Extract a formula to compute the index of the kt child node for a given node i, i.e. CHILD(i, k). Please show your work. Question 2 (15 POINTS): Given an array A- 22, 16, 13, 5, 12, 9, 0, 4, 6, 11) check whether this array preserves max-heap property. Please show your work

Explanation / Answer

1.A. PARENT(i) = (i-1)/2 1.B. CHILD(i,k) = 2*i + k 2. 22 / 16 13 / / 5 12 9 0 / 4 6 5 < 6 So, It is not a max-heap

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.