# Binary heap of size $n$ splitting to 2 heaps of size $n/2$ [closed]

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

• 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. – D.W. Jun 2 '14 at 6:22
• There is no question any more. – David Richerby Jun 2 '14 at 7:24
• Yes. You may close it now. – HaloKiller Jun 2 '14 at 7:30