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)$.
Binary heap of size $n$ splitting to 2 heaps of size $n/2$
algorithms;data structures;heaps