Consider the following algorithm for finding the “ith smallest element out of n

Question

Consider the following algorithm for finding the “ith smallest element out of n elements”:
(a) Place the first i elements into a data structure S.
(b) For each of the remaining elements, first insert the element into S, then remove the largest element from S. Thus, S always contains the “i smallest elements examined so far”.
(c) Return the largest element from S.

Discuss the pros and cons, including runtime analysis, of each of the following choices for the data structure S:
i. a red-black tree
ii. a min-heap
iii a max-heap

Which data structure would be best for S? Justify your answer.

Explanation / Answer

Best data structure to use is max-heap

Reason:

Building max heap on i element will take O(i) element

if next element if greater than root then we can ignore it else we need to heapify which will take O(log i)

so this overall will take O((n-i)*log i)

Finally root is the smallest element which will take O(1) to extract

so totall time: O(i + (n-i)*logi)

Min heap will take O(n + ilogn)

red black tree will take O(ilogi + (n-i)logi)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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