Use only C programming language format for the following questions. 1. Write in

ID: 3809999 • Letter: U

Question

Use only C programming language format for the following questions.

1. Write in pseudo-code the siftdown algorithm for a min-heap.

2. 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 pseudo-code the siftdown algorithm for a ternary max-heap.

3. Show that the algorithm in Question 2(ii) has worst-case complexity O(log n), where n is the length of the array.

2. 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 ?

ans:

i) Assuming the array starts at index 0.

The parent of a node at i is (i-1)/3

The children of a node at i are 3i+1,3i+2,3i+3.

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