1
$\begingroup$

Assuming a contiguous array implementation of a binary min heap with n elements, is it possible to remove the k-smallest elements in a faster time than $O(k \log n)$, as can be done via iteratively removing the minimum of the heap $k$ times?

More formally, by removal of k smallest elements, I mean removing the k smallest elements in the binary heap, ending up with a binary heap that does not have those k elements that have been removed, and a separate array that contains those k smallest elements (possibly unsorted).

$\endgroup$
4
  • $\begingroup$ I think that removing the $k$ smallest is not possible with the same reasoning as the answer, but just in case you are interested there is this SO question on finding the $k$ smallest in $O(k) $ time, which was a surprise for me. $\endgroup$
    – Russel
    Oct 31, 2022 at 13:35
  • $\begingroup$ Please define what you mean by "remove the k smallest". What do you want the output from the algorithm to be? A heap of all remaining $n-k$ elements? A list of all k smallest elements? Do they need to be in sorted order? It changes the question. What's the context where you ran into this task, and what's the motivation? $\endgroup$
    – D.W.
    Nov 1, 2022 at 2:14
  • $\begingroup$ @D.W. Do you wish me to edit the post? More formally, by removal of k smallest elements, I mean removing the k smallest elements in the binary heap, ending up with a binary heap that does not have those k elements that have been removed, and a separate array that contains those k smallest elements (possibly unsorted). I can add the above to the question if you wish. $\endgroup$
    – Jake1234
    Nov 1, 2022 at 22:00
  • $\begingroup$ Great, that's very clear! That sounds like it would be great to have in the question. To me, that highlights that no one has answered the question yet, as the existing answers only discuss how to find the smallest k elements, but don't discuss how to end up with a binary heap where those k elements have been removed. $\endgroup$
    – D.W.
    Nov 2, 2022 at 2:24

1 Answer 1

0
$\begingroup$

No, it is not possible: since it is possible to build a min-heap with $n$ elements in $\mathcal{O}(n)$ time, being able to remove $k$ elements in $o(k\log n)$ would result in a sorting algorithm in $o(n\log n)$ when removing $n$ elements.

Since a sorting algorithm must be $\Omega(n\log n)$ in the worst case, you have the answer.

Note that, as @Russel pointed it out in the comment, you could get the $k$ smallest unsorted elements in $\mathcal{O}(k)$ time.

$\endgroup$
2
  • 1
    $\begingroup$ Then sort them. $\mathcal O(k\log k)$ is better than $\mathcal O(k\log n)$. $\endgroup$
    – user16034
    Oct 31, 2022 at 15:14
  • $\begingroup$ Obviously you can remove the n smallest items in O(n) - just remove the complete heap; the result is obviously unsorted. So removing the k smallest elements in unsorted order in little-o (k log n) or even o(k log k) seems possible. $\endgroup$
    – gnasher729
    Nov 1, 2022 at 0:12

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.