A three-heap with n elements can be stored in an array A, 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 if 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.

d) Removing Arbitrary Items From Heaps One way to remove an 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.

e) Write pseudocode for an algorithm that performs the remove operation using the alternative approach described above. Your pseudocode should implement the method call 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 described in lecture: insert, deleteMin, percolateUp, and percolateDown. Like in lecture, you may assume that objects are just priority integers (no other data).

f) What is the worst case complexity of the algorithm you wrote in part (a)?