0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – ryan
    Commented Jul 29, 2019 at 4:25
  • 3
    $\begingroup$ 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! $\endgroup$
    – ryan
    Commented Jul 29, 2019 at 4:26
  • $\begingroup$ 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. $\endgroup$
    – NightDriveDrones
    Commented Jul 29, 2019 at 10:13

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.