2
$\begingroup$

Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ time. This can be improved to $O(k \log k)$ time by maintaining a separate heap $H'$ as follows. Start by inserting the root of $H$ in $H'$. Then when performing a delete-min operation, you add both children of that node in $H'$, and repeat until you have all $k$ elements. Is there a way to do better? I have a feeling that $O(k)$ should be possible, but I can't come up with an algorithm - though certainly you cannot hope to do better than $\Omega(k)$.

Edit: I would just like a hint please.

$\endgroup$
4
$\begingroup$

If you mean the usual binary heap represented in an array, this is answered in "An Optimal Algorithm for Selection in a Min-Heap", by Frederickson. It is pretty complex.

Other priority queues have easier algorithms. For instance, if you use a threaded AVL tree as priority queue, you can just follow right neighbor pointers from the minimum value.

$\endgroup$
  • $\begingroup$ Thanks! This was a given to me as a bonus question. I won't be answering it anymore, but thank you for the reference! $\endgroup$ – user340082710 Mar 6 '16 at 4:22
  • 1
    $\begingroup$ re: "This was given to me as a bonus question": you shouldn't get outside help on your homework without permission from your instructor. $\endgroup$ – jbapple Mar 6 '16 at 4:26
  • $\begingroup$ It's fine if I reference my sources. I wouldn't have posted otherwise. $\endgroup$ – user340082710 Mar 6 '16 at 4:34

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.