Split Binomial Heap

I'm trying to think of an ide开发者_Go百科a to make a new Split operation that By given a Binomial heap.

The question is how to split binomial heap (size n) into binomial heap of size k (k < n), and binomial heap of size n-k within the minimal time of running.

You can find the kth largest element of a set in O(n) time with the median of medians algorithm. Source.

When you have that value, you can read all values from the original heap (don't need to extract, their order doesn't matter on read, only on write in the new arrays. This has the added benefit of not messing with the original heap. Yay.) and put into the large or small heap, depending on their relation to the kth value. Each extraction is O(1) and occurs n times. Each insert is O(lg n) and occurs n times.

Total running time: n +  n  + n lg n = O(n lg n)
                    |    |       |
             selection   |    inserts
                     extraction

You can do this in k*log(n) by simply removing k elements from the original heap and moving them to a new different heap. (this assuming the heap is a minimum heap, if it's a maximum heap then it can be done the same way in (n-k)log(n))

Because the binomial heap's trees can be represented as the binary digits of n, you can split the heap in O(log(n)) simply by doing a binary long subtraction between n and k where each time you need to "borrow" a digit what you split in half one tree. it's exactly like binomial trees merge but using a binary long subtraction instead of addition on the trees.