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 775 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 Show 9 previous comments 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.