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?

$\endgroup$
  • $\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 Jul 29 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 Jul 29 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 Jul 29 at 10:13
1
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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