The Gateway to Computer Science Excellence
+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?
in Algorithms by Active (2k points) | 249 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.
by Active (2k 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).
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
50,650 questions
56,228 answers
95,681 users