(You may assume that lg n divides n such that n/ lg n is an integer.) You are gi

Question

(You may assume that lg n divides n such that n/ lg n is an integer.) You are given an array A[1..n] of n keys appearing in an arbitrary order. We would like to find the n/ lg n largest of them and output them in sorted order (smallest to largest). Provide a time and space efficient algorithm that outputs the keys in A[1..n/ lg n] (of the n positions available).

(You may assume that lgn divides n such that n/lgn is an integer.) You are given an array A[1..n] of n keys appearing in an arbitrary order. We would like to find the n/lg n largest of them and output them in sorted order (smallest to largest). Provide a time and space efficient algorithm that outputs the keys in All..n/lgn] (of the n positions available)

Explanation / Answer

This is just a variation of k largest element in an array with k being n/logn

You can use min heap to do it

Time comlpexity = O(k + (n-k)*Logk) replace k with n/logn

and space comllexity is O(k)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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