3
$\begingroup$

I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it?

(Calling deletemax $k$ times yields a $O(k \log n)$ complexity. I'm looking for $O(k \log k)$.)

The only solution I've come up with so far is the following:

You have 2 arrays. A(largest numbers), B(to analyze).

  • It's easy to find the largest number, since we already have the heap. We move the maximum number to $A$.
  • We move the maximum number's children to $B$
  • We sort $B$
  • We add the children of the largest number in $B$
  • Remove the largest number from B (first element of $B$), add it to $A$
  • Repeat the procedure until there are $k$ elements in $A$

The question here is: do we get a $O(k \log k)$ complexity? we obviously repeat the procedure $k$ times, but does the sorting take $O(\log k)$ time? I guess if the array is already sorted it's easy to insert a new number in $O(\log k)$ time. However, will the length of array B always be less than or equal to $k$?

Can you please confirm or deny my solution? If it's wrong, can you please help me find a solution to this problem?

$\endgroup$
  • $\begingroup$ By determine you mean storing largest number, deleting it and reorganizing the heap? $\endgroup$ – user1563544 Oct 22 '14 at 4:16
  • $\begingroup$ I know what deletemax() does. deletemax() takes log(n) time. performing it k times will take klog(n) time. I'm trying to find an algorithm with klog(k) complexity. $\endgroup$ – user1563544 Oct 22 '14 at 4:23
  • $\begingroup$ 1. Sorry, I misunderstood. 2. "Can you confirm my solution?" questions are not a good fit for this site. 3. Why would you expect sorting to take $O(\log k)$ time? I suspect you should be thinking about this as inserting into an already-sorted list, not as sorting a list. $\endgroup$ – D.W. Oct 22 '14 at 4:29
0
$\begingroup$

Hint: Each time you perform one iteration of your loop, how much does the size of $B$ increase? Each time you perform one iteration of your loop, how many numbers are added to $A$?

You terminate once $k$ integers have been added to $A$... so how many times will the loop iterate? What does this tell you about how large $B$ can get? What does that say about the running time of your algorithm?

(I am giving only a hint, so you can have the pleasure of working out the answer on your own.)

$\endgroup$

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.