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$

closed as unclear what you're asking by D.W., David Richerby, FrankW, Raphael Jun 2 '14 at 12:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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