Data structure

2 4 Data Structures Consider a data structure for maintaining a multi-set M (that is, an unordered set where each element may appear more than once). We want to support the following operations: . Init(M): create an empty data structure M . Insert(M, i): insert (one copy of) i in M . Remove(M, i): remove (one copy of) i from M e Frequency(M,i): return the number of copies of i in M o Select(M, k): return the kth element in the sorted order of elements in M If for example M consists of the elements (0,3,3,4, 4,7,8,8,8,9,11, 11, 11,11, 13) then Frequency(M, 4) will return 2 and Select(M, 6) will return 7. Let |M| and Mll denote the number of elements and the number of different elements in M, respectively. (a) Describe an implementation of the data structure such that Init(M) takes O(1) time and all other operations take O(log M) time. (b) Design an algorithm for sorting a list L in O(L log |L) time using this data struc- ture