Please answer the full question and write legibly

Problem 3 (20 points). Consider a priority queue that supports INSERT and EXTRACT-MAX operations. Given a sequence of these operations on a set of keys {1...n}, we would like to record the sequence of extracted elements from the priority queue, storing them in an array ertracted. The entire operation sequence may be processed in advance before reporting the extracted sequence. (a) In the following operation sequence S, each value i represents INSERT(i) and each 'E' represents an EXTRACT-MAX call: S = 7,1, E, 3,9, E, E, 2, E, E,4,8, E,5,6 Give the correct values in the extracted array. (b) To develop an algorithm for this problem, we break into homogeneous operation subsequences: S = 11, E, 12, E,..., Im, E, Im+1; where each 'E' is a single EXTRACT-MAX call and each I, represents a (possibly empty) sequence of INSERT calls. For each I, we initially place the keys inserted by that subsequence of operations into a set Ky, which is empty if I, is empty. We then have the following algorithm: PRIORITY-QUEUE-EXTRACTIONS(m, n) 1: for i = n downto 1 do 2: Determinej such that i EK 3: if i m + 1 then 4: extracted[ ] = i 5: Let l be the smallest value greater than j for which Ki exists 6: Ki=K, UK, destroying K 7: return ertracted Describe how to implement PRIORITY-QUEUE-EXTRACTIONS efficiently with a disjoint set data structure. (e) Give a tight bound on the worst-case running time of your implementation. Justify your