1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mickey Jul 29 '17 at 18:57
  • $\begingroup$ @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$. $\endgroup$ – md5 Jul 29 '17 at 19:02
  • $\begingroup$ Nice! thanks, great implementation, simple explanation. $\endgroup$ – Mickey Jul 29 '17 at 19:11

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.