Use only C programming language for the following questions. 1.A ternary max-hea

Question

Use only C programming language for the following questions.

1.A ternary max-heap is similar to the binary max-heap that we have discussed in class, but now non-leaf nodes can have 3 children instead of 2.

(i) A ternary max-heap can be represented using an array. What are the indices of the parent and children of a node at index i ?

(ii) Write in pseudocode the siftdown algorithm for a ternary max-heap. 3. Show that the alogorihm in Question 2(ii) has worst-case complexity O(log n), where n is the length of the array.

Explanation / Answer

1 ) a) The indices of the parent and children of a node at index i are given by ,

PARENT(i) = i/2

LEFT CHILD(i) = 2i

RIGHT CHILD(i) = 2i+1

b) Pseudocode :

3. In the siftdown algorithm each node is compared to its childern and one of them will be chosen as the next root node , after each siftdown call one level of the tree will be dropped to each next step in the process , The maximum number of levels in the heap will be log n , therefore the worst case complexity for n length array is O(log n) .

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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