Suppose you have k non-empty sorted doubly-linked lists L1, . . . , Lk,where n = |L1| + . . . + |Lk|. You are to design a data structure that supports both remove-min and remove-max in O(log k) time on the union of the lists; i.e., these operations act on the elements that have not been deleted so far from the data structure. We will only be removing elements, so you don’t have to handle insertions. You are allowed O(k) time to initialize the data structure and you are not allowed to modify the lists (you can traverse them but you are not allowed to add or remove elements from them). For full marks, you need to meet all these requirements.

a) Describe your data structure, i.e., the structure and its operations.

b) Briefly argue the correctness of your operations.

c) Analyse the running time of your operations