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$
4
  • $\begingroup$ By determine you mean storing largest number, deleting it and reorganizing the heap? $\endgroup$ Oct 22, 2014 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$ Oct 22, 2014 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, 2014 at 4:29
  • $\begingroup$ Answered here with $k=log n$ cs.stackexchange.com/questions/79472/… $\endgroup$
    – MERTON
    Jan 22 at 17:56

1 Answer 1

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$
0

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.