# Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access...

My question though is, when we have an implicit array representation of a min-heap, e.g.:

min_heap = [1, 2, 4, 3, 6, 5, 54, 12, 12, 34]


In this case, is it possible to infer the Kth-smallest value's index from the value of K, so you can use the array index to get the value in O(1) time?

• No, not in general. For instance, finding the $n$th smallest element (the largest element) will take at least $\Omega(n)$ in the worst case. Similar argument to what's given here.
– ryan
Jul 29, 2019 at 4:25
• Another reason for No. If this is the case then we could extract a sorted list in linear time $O(1)$ for each $k$th smallest element. We can also create a min heap in linear time thus we could sort in linear time!
– ryan
Jul 29, 2019 at 4:26
• Great point, I never looked at it that way. If this were possible, it would enable things that are clearly impossible, therefore it must not be possible. Jul 29, 2019 at 10:13

This is not possible. If this is the case then we could extract a sorted list in linear time; $$O(1)$$ for each $$k$$th smallest element. We can also create a min heap in linear time thus we could sort in linear time! We know comparison sorting has an $$\Omega(n \log n)$$ lower bound worst case, so this is not possible.