3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Related: cs.stackexchange.com/q/32181/83244 $\endgroup$ – xskxzr Jul 10 at 16:08
  • $\begingroup$ Given a binary heap of size n and a number k≤n min-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
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @royashcenazi If you repeatedly pop from the original heap you end up with $O(k \log n)$ instead of $O(k \log k)$. $\endgroup$ – orlp Jul 10 at 15:49
  • $\begingroup$ Got it, thanks. $\endgroup$ – royashcenazi Jul 10 at 18:10

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.