Consider the following algorithm for finding the ith smallest element out of n elements: (a) Place the first i elements into a data structure S. (b) For each of the remaining elements, first insert the element into S, then remove the largest element from S. Thus, S always contains the i smallest elements examined so far. (c) Return the largest element from S.

Discuss the pros and cons, including runtime analysis, of each of the following choices for the data structure S: i. a red-black tree ii. a min-heap iii a max-heap

Which data structure would be best for S? Justify your answer.