Priority queues: Consider the following code fragment. Assume that a[ ] is an ar

Question

Priority queues:

Consider the following code fragment.

Assume that a[ ] is an array of integers, MaxPQ is implemented using a binary heap, and N ? k ? 1.

(a) What does it output?

(b) What is the order of growth of its worst-case running time. List the best answer: (k log k, k logN, N log k, N logN, N2)

(c) Now suppose the marked line was deleted. Repeat the previous two questions.

(d) What does it output?

(e) What is the order of growth of its worst-case running time. List the best answer. (k log k, k logN, N log k, N logN, N2)

Even if you can't answer all of the parts, any help is appreciated. I am totally lost :(

Explanation / Answer

1) What does it ouput?
=> It will return k smallest number in the array in descending order;
if a = [1,5,3,4,2] and k = 2; output will be 2,1

2) What is the order of growth of its worst-case running time.
=> N log k

3,4,5) Now suppose the marked line was deleted.
=> output will be sorted Non-decreasing Array
if a = [1,5,3,4,2] and k = 2; output will be 5,4,3,2,1
=> N log N

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.