# Splitting a binomial heap into 3n/8 and 5n/8 binomial heap whereas 8 divides n with O(log(n)) time

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?

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.