CODEWITHSUNDEEP
data-structures
Unknown user
Unknown user

Reputation: 45301

Split Binomial Heap

I'm trying to think of an idea 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.

Upvotes: 2

Views: 1527

Answers (3)

Tᴏᴍᴇʀ Wᴏʟʙᴇʀɢ
Tᴏᴍᴇʀ Wᴏʟʙᴇʀɢ

Reputation: 102

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.

Upvotes: 0

corsiKa
corsiKa

Reputation: 82559

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

Upvotes: 1

Gal
Gal

Reputation: 5416

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))

Upvotes: 0

Related Questions