5 votes 5 votes DS data-structures binary-heap test-series time-complexity + – ankitgupta.1729 asked Nov 9, 2017 retagged Jul 7, 2022 by Lakshman Bhaiya ankitgupta.1729 777 views answer comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 27, 2017 reply Follow Share Useful read for 1st statement https://stackoverflow.com/questions/5380568/algorithm-to-find-k-smallest-numbers-in-array-of-n-items 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes yes all are correct! In first case to find the kth largest element, do k-1 deletions from the max heap, so k-1 times max-heapify procedure will be called. T.C (k-1)logn = O(klogn) Manu Thakur answered Nov 9, 2017 selected Nov 10, 2017 by ankitgupta.1729 Manu Thakur comment Share Follow See all 12 Comments See all 12 12 Comments reply joshi_nitish commented Nov 10, 2017 reply Follow Share @Manu, for (ii), i think it will take O(n+klogn)........ since n/2 minimum elements are present in leaves of a max heap, now you have to find kth minimum among them, you can work it like this, create min heap for that n/2 elements -> O(n) perform extract_min for k times -> O(klogn) in total it will take-> O(n+klogn), though if k is some constant, answer will be O(n), but in worst case k can be of O(n).. therefore i think in worst case to find kth min in max heap will take -> O(n+klogn) 0 votes 0 votes joshi_nitish commented Nov 10, 2017 reply Follow Share and also one more thing, it might be case that kth min is not even in leaf, because leaf contains about n/2 keys, what if it is saying to find (n/2+5)th minimum.. 0 votes 0 votes ankitgupta.1729 commented Nov 10, 2017 reply Follow Share @Manu Thakur, Got it.. Thanks a lot :) 0 votes 0 votes Manu Thakur commented Nov 10, 2017 reply Follow Share @nitish yes you are right answer should b O(n + klogn) but they explicitly mentioned that k is less than n, and if we believe that it's some constant and n value is huge, we can go for O(n) T.C 0 votes 0 votes joshi_nitish commented Nov 10, 2017 reply Follow Share but less than doesn't mean that it is some constant, k could be {n-4, n-6 , n/2 , n/4}, all these values are <n and also even O(n) 0 votes 0 votes hs_yadav commented Nov 10, 2017 reply Follow Share for that case take all n elements of max heap and build a min heap...and then perform kth min. operation... T(n)=O(n)+O(klogn) 0 votes 0 votes Manu Thakur commented Nov 10, 2017 reply Follow Share @nitish i am not denying this possibility what you said. 0 votes 0 votes joshi_nitish commented Nov 10, 2017 reply Follow Share @hs_yadav yes, exactly i was also saying this...in worst case it will take O(n+klogn).. it will take O(n) time only when in qsn it is explcitly mentioned that k is some constant. 0 votes 0 votes joshi_nitish commented Nov 10, 2017 reply Follow Share @Manu most appropriate answer then should be (i) and (iii) only...isn't it?? 0 votes 0 votes Sandeep Suri commented Nov 10, 2017 reply Follow Share Option (ii) is also okay as K is less than number of element 0 votes 0 votes joshi_nitish commented Nov 10, 2017 reply Follow Share @Sandeep Suri please read above comments first. 0 votes 0 votes Warlock lord commented Nov 21, 2017 reply Follow Share It's looking for a minimum element in a MAX Heap. Why are you deleting the items here and heapifying again? In any case it should take maximum O(n) T.C 0 votes 0 votes Please log in or register to add a comment.