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