# Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?

The simplest solution would be using $\text{Get-Min, Delete-Min}$, $\log n$ times, and that would be of time complexity of $O(\log ^2 n)$.

I've been told that this problem can be solved in time complexity of $O(\log n \log \log n)$, but I couldn't figure out an algorithm that reaches that time complexity.

Consider another min-priority queue $q$. The result will be in array $a$.

• Push the top of the heap into $q$.
• For $i$ from $1$ to $\log n$:

• Set $a_i = \text{pop}(q)$.
• Push the two sons of $a_i$ in the heap into $q$.

$q$ may be implemented with a min-heap of size $O(\log n)$, so the overall complexity is $O(\log n \log \log n)$.

• What guarantees me that the two sons of $a_i$ both belong to the smallest $\log n$ elements? I can be sure for one of them - but the other might be much bigger. – Mickey Jul 29 '17 at 18:57
• @Mickey: That's why we are keeping them in a min-priority queue. At the end of the loop on $i$, there might remain elements in $q$ that we inserted previously but who are not in the smallest $\log n$ elements. If you visualize your heap as a tree, at each time,. for all path from the node to a leaf in the initial heap, there exists exactly one node on this path in $q$. – md5 Jul 29 '17 at 19:02
• Nice! thanks, great implementation, simple explanation. – Mickey Jul 29 '17 at 19:11