Algorithms Running Median

In this task you wil design a data structure supporting the following operations BUILD(An): Initializes the data structure with the elements of the array A. INSERT(x): Inserts the element into the data structure MEDIAN: Returns the median 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.) 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 (c) (3 points) INSERT running in time O(log n), where n is the number of elements in the data running time. structure. O(n)) structure. (d) (3 points) MEDIAN running in timeO( In this task you wil design a data structure supporting the following operations BUILD(An): Initializes the data structure with the elements of the array A. INSERT(x): Inserts the element into the data structure MEDIAN: Returns the median 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.) 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 (c) (3 points) INSERT running in time O(log n), where n is the number of elements in the data running time. structure. O(n)) structure. (d) (3 points) MEDIAN running in timeO(