Problem 2.

Two Binary Min Heap Algorithms For both of these problems, for full credit your solution should be the most efficient possible. Perhaps in the worst case they might need to examine every element in the heap, but in general this should not be the case. You may assume an array layout of the binary min heap as discussed in lecture. You also may assume that your algorithm has direct access to the heap array (it does not need to manipulate it just by using the standard heap operations insert, deletemin, findmin, etc.). Your algorithm should not modify the heap (just like a findmin does not modify the heap) or at the very least, if it does, it should put it back identical to how it was before you started. Be sure to answer all four parts (a-d) of the question!

a) Write pseudocode for an efficient algorithm that will find the maximum value in a binary min heap.

b) What is the worst case complexity of the algorithm you wrote in part (a)? Give your answer in big-O.

c) Write pseudocode for an efficient algorithm that will find all values less than a given value in a binary min heap. Your algorithm should just print out the values it finds. Note that the given value" is not necessarily in the heap. We could ask you to find all values less than 42 in the heap, where the value 42 is not in the heap.

d) What is the worst case complexity of the algorithm you wrote in part (c)? Give your answer in big-O. What is the runtime of your algorithm if it finds k values less than the input value?