The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 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?
asked in Algorithms by Active (1.7k points) | 149 views
I think its O(n) because you have to go through the N/2 to N part of the heap.
Yeah, the nth largest element will be present in one of the leaf nodes, which will take $O(n)$
Yes, It will be O(n).

1 Answer

+1 vote
Best answer
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.
answered by Active (1.7k points)
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.?
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).

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
68,742 users