Consider the following simple approach to the priority queue problem that completely avoids the use of trees: choose a parameter r, divide the set into r groups of size at most ⌈n=r⌉, and store the minimum of each group.
(a) [12 marks] Using this approach, describe how to
• preprocess the data structure in O(n) time,
• support fi nd-min and delete-min in O(r + n=r) time, and
• support decrease-key (changing an element to a smaller value) in O(1) time.
(b) [2 marks] Describe how to choose the parameter r to minimize the above runtime of fi nd-min/delete-min.
(c) [2 marks] How do the above runtimes for preprocessing, delete-min, and decrease-key compare with those for the standard heap?