The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
92 views
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 Junior (893 points) | 92 views
0
I think its O(n) because you have to go through the N/2 to N part of the heap.
+1
Yeah, the nth largest element will be present in one of the leaf nodes, which will take $O(n)$
+1
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 Junior (893 points)
0
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
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

47,003 questions
51,322 answers
177,487 comments
66,667 users