A three$-$heap with $n$ elements can be stored in an array $A_s$ where $A[0]$ contains the

root of the tree.

a$.$ Draw the three$-$heap that results from inserting $5,2,8,3,6,4,9,7,1$ in that

order into an initially empty three$-$heap. You do not need to show the array

representation of the heap. You are only required to show the final tree,

although you draw intermediate trees.

b$.$ Assuming that elements are placed in the array starting at location $A[0],$

give expressions to calculate the left, middle, and right children of the

element stored in A$[$i$]$:

Left child:

Middle child:

Right child:

c$.$ Draw the array representation of your heap from part b$.$

Removing Arbitrary Items from Heaps: One way to remove any object from a binary

min heap is to decrease its priority value by $1$ and then call deletemin. An alternative

is to remove it from the heap, thus creating a hole, and then repair the heap.

a$.$ Write pseudocode for an algorithm that performs the remove operation using

the alternative approach described above. Your pseudocode should

implement the method named remove $($int index$),$ where index is the index

into the heap array for the object to be removed. Your pseudocode can call

the following methods: insert, deleteMin, percolateUp, and percolateDown.

You may assume that objects are just priority integers $($no other data$).$

b$.$ What is the worst$-$case complexity of the algorithm you wrote in part $($a$)?$