1 1 vote What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap? Data Structures data-structures binary-heap time-complexity + – gmrishikumar 3.3k views answer comment Share Follow Print See all 4 Comments 4 4 Comments reply gmrishikumar commented Dec 1, 2018 reply Follow flag I think its O(n) because you have to go through the N/2 to N part of the heap. 1 1 replyShare goxul commented Dec 1, 2018 reply Follow flag Yeah, the nth largest element will be present in one of the leaf nodes, which will take $O(n)$ 1 1 replyShare kumar.dilip commented Dec 1, 2018 reply Follow flag Yes, It will be O(n). 1 1 replyShare reboot commented Jan 4, 2021 reply Follow flag https://www.geeksforgeeks.org/maximum-element-in-min-heap/ 0 0 replyShare Please log in or register to add a comment.
Best answer 2 2 votes The nth largest element will be present in one of the leaf nodes, and will take O(n/2) time to find. Therefore O(n) is the required complexity. gmrishikumar answered Dec 1, 2018 gmrishikumar comment Share Follow See all 2 Comments 2 2 Comments reply Sweta Shaw commented Dec 24, 2018 reply Follow flag Suppose the min heap has elements 1,2,3,4,5 ,6 in that order . And we want to find 4th largest element. How can you say the 4th largest element will be present in the leaves.? 0 0 replyShare gmrishikumar commented Dec 26, 2018 reply Follow flag I am not saying that all elements are present in the leaves. Obviously some elements will not be leaves and will be Kth largest element in heap. If element is not in the leaves we won't need O(n) time. We will need less than that. But if the element is present in the leaf nodes we will need O(n/2) time and hence time complexity is O(n). 0 0 replyShare Please log in or register to add a comment.
