Problem 4 (20 points). Consider a priority queue that supports INSERT and ExTRACT-MAx operations. Given a sequence S 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 ertracted array. bTo develop an algorithm for this problem. we break s into homogeneous operation subsequences: 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 Kj, which is empty if I is empty. We then have the following algorithm: PRIORITY-QUEUE-ExTRACTIONS (m, n) 1: forin downto 1 do 2 Determine j such that i EK if Jm + 1 then etractedj]i 5: Let l be the smallest value greater than j for which Ki exists 6: 7: return ertracted Ki-K,UKI, destroying K, Argue that the array extracted returned by PRIORITY-QUEUE-ExTRACTIONS is correct c. Describe how to implement PRIORITY-QUEUE-ExTRACTIONS efficiently with a disjoint set data structure. d. Give a tight bound on the worst-case running time of your implementation. Problem 4 (20 points). Consider a priority queue that supports INSERT and ExTRACT-MAx operations. Given a sequence S 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 ertracted array. bTo develop an algorithm for this problem. we break s into homogeneous operation subsequences: 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 Kj, which is empty if I is empty. We then have the following algorithm: PRIORITY-QUEUE-ExTRACTIONS (m, n) 1: forin downto 1 do 2 Determine j such that i EK if Jm + 1 then etractedj]i 5: Let l be the smallest value greater than j for which Ki exists 6: 7: return ertracted Ki-K,UKI, destroying K, Argue that the array extracted returned by PRIORITY-QUEUE-ExTRACTIONS is correct c. Describe how to implement PRIORITY-QUEUE-ExTRACTIONS efficiently with a disjoint set data structure. d. Give a tight bound on the worst-case running time of your implementation
