Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

image text in transcribed

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Design Using Entity Relationship Diagrams

Authors: Sikha Saha Bagui, Richard Walsh Earp

3rd Edition

103201718X, 978-1032017181

More Books

Students also viewed these Databases questions