In this task you will design a data structure supporting the following operations BUILD(A1..n): Initializes the data structure with the elements of the array A INSERT(x): Inserts the element r into the data structure MEDIAN: Returns the median1 of the currently stored elements In the following, you are allowed to use the standard heap operations from CLRS Chapter 6 (incurring the corresponding running times) (a) (4 points) Describe in English an idea for a data structure such that you can perform the operations BUILD, INSERT, and MEDIAN with running times as required below. Do not formally analyze the running time yet (Hint: Use a min-heap and a max-heap.) Solution: INSERT YOUR SOLUTION HERE In parts (b)-(d), describe in pseudo-code your implementations from part (a) and analyze the (b) (3 points) BUILD running in time O(n), where n is the number of elements in the data (Hint: Use the FIND-MEDIAN algorithm given in class to find the median of a list in time running time structure Solution: INSERT YOUR SOLUTION HERE Using three-way partitioning ensures that duplicates do not cause trouble. Do not deduct points if a student's solution does not handle duplicates properly (point it out to them though) (c) (3 points) INSERT running in time O(log n), where n is the number of elements in the data structure Solution: INSERT YOUR SOLUTION HERE (d) (3 points) MEDIAN running in time O(1) Solution: INSERT YOUR SOLUTION HERE