# Removing k-smallest elements in a binary min-heap

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).

• 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. Commented Oct 31, 2022 at 13:35
• 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?
– D.W.
Commented Nov 1, 2022 at 2:14
• @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. Commented Nov 1, 2022 at 22:00
• 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.
– D.W.
Commented Nov 2, 2022 at 2:24

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.
• Then sort them. $\mathcal O(k\log k)$ is better than $\mathcal O(k\log n)$.