Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end?
The problem is that the time-complexity needs to be $\Theta(k \log(k))$.
Construct a new min-heap $H$ using the root of the original heap $O$ as its only element. Then $k$ times you want to pop the smallest value from $H$, append it to our output array and add the children that node has in $O$ to $H$.
The maximum size $H$ gets here is $k + 1$, so all the above has a complexity of $O(k \log k)$.
If you meant to keep the original heap intact, you are now done. If you also want to remove these $k$ elements from $O$, then all you need to do is use $H$ as your new heap, making any leaf of $H$ use the child pointers that respective node had in $O$.
All of the above is assuming you have a pointer-based tree structure. If you use an array as your heap data structure using indices as implicit children, I doubt it's possible at all.
On top of that, this optimization is likely not worth it unless $n$ is very large and $k$ is very small.
Given a binary heap of size n and a number k≤nmin-heap or max-heap? What operations does this heap support? What, if applicable, any of its nodes? Upper bounds on resource usage of each operation? If linked: is the depth of any leaf guaranteed to be no lower than $k$? $\endgroup$ – greybeard Jul 11 at 2:22