2
$\begingroup$

Input: A binary heap of size $n$. $n$ is even.
Output: 2 binary heaps of size $n/2$ each.

I found this question in a solved algorithms test and the solution said: "There is no better solution than to build 2 completely new heaps using BuildHeap() - $O(n)$ time."

I have thought about taking out the root out of the original heap, and then we have 2 sub-heaps, one with $\lfloor n/2 \rfloor$ values, and one with $\lfloor n/2 \rfloor +1$ values. Now we just add the element we took out to the bigger heap of the two sub-heaps. How do we know which heap is bigger?
We traverse the heap with 2 pointes, Left and Right. Left that goes only left, and Right that goes only right, and every pointer has a counter that counts the number of elements is has passed. The bigger heap will be denoted by the max counter of the 2 pointers.
This works because a binary heap by definition is full in all of it's levels, aside the last level, which is full from left to right.
That sums up to $O(log n)$.

My question is: Am I right, or is the solution right?

Edit: My solution is wrong. I have tough about adding it a fix but it makes it $O(n)$.

$\endgroup$
  • $\begingroup$ Is your question resolved now, or is there anything remaining to be asked? In the future, please don't just tack on "Edit: never mind everything above" at the end -- please edit the question so it stands on its own. $\endgroup$ – D.W. Jun 2 '14 at 6:22
  • 1
    $\begingroup$ There is no question any more. $\endgroup$ – David Richerby Jun 2 '14 at 7:24
  • $\begingroup$ Yes. You may close it now. $\endgroup$ – HaloKiller Jun 2 '14 at 7:30