1 votes 1 votes 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? DS data-structures binary-heap time-complexity + – gmrishikumar asked Dec 1, 2018 recategorized Jul 6, 2022 by Lakshman Bhaiya gmrishikumar 2.3k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply gmrishikumar commented Dec 1, 2018 reply Follow Share I think its O(n) because you have to go through the N/2 to N part of the heap. 1 votes 1 votes goxul commented Dec 1, 2018 reply Follow Share Yeah, the nth largest element will be present in one of the leaf nodes, which will take $O(n)$ 1 votes 1 votes kumar.dilip commented Dec 1, 2018 reply Follow Share Yes, It will be O(n). 1 votes 1 votes reboot commented Jan 4, 2021 reply Follow Share https://www.geeksforgeeks.org/maximum-element-in-min-heap/ 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 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 See all 2 2 Comments reply Sweta Shaw commented Dec 24, 2018 reply Follow Share 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 votes 0 votes gmrishikumar commented Dec 26, 2018 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.