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