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 extracted. The entire operation sequence may be processed in adva nce before reporting the extracted sequen ce 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.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 S into homogeneous operation subsequences S- 11, E, I2, E,..., Im, E, Im where each 3' is a single EXTRACT-MAX call and each li represents a (possibly empty) sequence of INSERT calls. For each Ij, we initially place the keys inserted by that subsequence of operations into a set Kj, which is empty if Ij is empty. We then have the following algorithm PRIOrITY-QUEUE-ExTRACTIONS(m, n) 1: for i -n downto 1 do 2: Determine j such that iE Kj 3: if j m1 then 4 5: 6: 7: return ertracted extractedlj]-i Let l be the smallest value greater than j for which Ki exists Ki K,U Ki, destroying Kj Argue that the array extracted returned by PRIORITY-QUEUE-EXTRACTIONs is correct 2 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 extracted. The entire operation sequence may be processed in adva nce before reporting the extracted sequen ce 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.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 S into homogeneous operation subsequences S- 11, E, I2, E,..., Im, E, Im where each 3' is a single EXTRACT-MAX call and each li represents a (possibly empty) sequence of INSERT calls. For each Ij, we initially place the keys inserted by that subsequence of operations into a set Kj, which is empty if Ij is empty. We then have the following algorithm PRIOrITY-QUEUE-ExTRACTIONS(m, n) 1: for i -n downto 1 do 2: Determine j such that iE Kj 3: if j m1 then 4 5: 6: 7: return ertracted extractedlj]-i Let l be the smallest value greater than j for which Ki exists Ki K,U Ki, destroying Kj Argue that the array extracted returned by PRIORITY-QUEUE-EXTRACTIONs is correct 2 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
