[Solved]: Find k maximum numbers from a heap of size n in O(klog(k)) time

Problem Detail: 

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?

Asked By : user1563544

Answered By : D.W.

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32181