# Returning sorted lowest k elements in a binary heap

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

• – xskxzr Jul 10 '19 at 16:08
• 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$? – greybeard Jul 11 '19 at 2:22

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.

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