0
$\begingroup$

I ran into this exercise that says:

With a given binomial heap with n elements and n is divisible by 8, split the heap into 2 binomial heaps, one with 3n/8 elements and the other with 5n/8 elements.

I tried using another heap as a helping heap that saves the heaps I need to merge, but I didn't exactly know how to split. Then I tried to use a stack and a queue, and I didn't get anywhere either. Can someone please help with this?

$\endgroup$

1 Answer 1

3
$\begingroup$

If $n$ is even, you can split the heap into two heaps of size $\dfrac{n}2$:

For each binomial tree in the heap, remove its first child; reconstruct a heap with all the children you removed.

Since a binomial heap has at most $\mathcal{O}(\log n)$ binomial trees, this operation is done in $\mathcal{O}(\log n)$.

Using the same idea several times, you can split the heap into:

  • two heaps of size $\dfrac{n}8$
  • one heap of size $\dfrac{n}4$
  • one heap of size $\dfrac{n}2$

Now just merge (in $\mathcal{O}(\log n)$) two pairs of those and you get the result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.