Creating a binomial heap from an array?

Question

When creating a binomial heap, i am aware that the general procedure is to first create a head pointing to nil and slowly insert 1-node heap and unite heaps with same degree based on 4 cases.

However, I would like to ask given an array of a size n, Is it possible that since there are at most floor(lg n) + 1 binomial trees, we partition the array based on number of trees, 2^0, 2^1, 2^2 so on and so forth, and within each binomial tree bubble up so that each tree fulfills minheap property?

so for example: given the array [4, 10, 8, 20, 5, 1, 3]

1. If inserted one by one, root list is 3, 1 and 4. 1 has child 5; 4 has child 8 and 10 and 8 has child 20.
2. In the other case: we have root list 4, 8 and 1. 8 has child 10; 1 has child 3 and 20, 3 has child 5.

if done in this way, would it defeat the whole purpose of the binomial heap?

Answer 1

It seems like you have three separate questions here.

1. Can you use the approach you're describing to build a binomial heap from an array?
2. Is it a problem that you get different binomial heaps back from your procedure versus what you'd get if you added elements into an empty binomial heap one at a time?
3. Is this a worthwhile thing to do?

Let's go over each of them one at a time.

Does this approach work?

Yes! This is a perfectly valid way to build a binomial heap. The rules for binomial heaps only require that (1) there are no two trees of the same size and (2) each tree is heap-ordered. So in that sense, any procedure that gets you from a collection of elements into a collection of heap-ordered binomial trees of different sizes will work.

Is it bad that we don't get the same heap?

No, that's not a problem at all. You are correct that you'll get different a binomial heaps back if you proceed this way. But you also could have gotten a different heap back by adding the elements in from the array in a different order as well. For example, if you use the normal insertion algorithm and add the elements from the original array in sorted order, the heap you'd get would have a different shape from the heap you'd get from proceeding left to right. (And that heap has a different shape from the one you'd get by proceeding right to left.) Reasoning by analogy to a binary heap - you can have lots of different binary heaps that all have the same elements, just in a different order.

Is this worthwhile?

Compared with binary heaps, binomial heaps have two advantages:

1. Inserting a sequence of n values into an empty binomial heap one at a time takes time O(n) in the worst-case; inserting n elements one at a time into an empty binary heap can take time Θ(n log n).
2. They support efficient melding. You can meld two binomial heaps in time O(log n), whereas with binary heaps that takes time O(n).

In the case you're describing, where all the elements are given to you in advance, advantage (1) isn't relevant because you could also build a binary heap from those elements in time O(n) using the heapify algorithm.

Similarly, if you choose to represent binomial heaps using an implicit array representation, you lose the ability to do fast melding, since the fast melding operation requires the trees to be represented using pointers and linked cells so that objects don't need to be moved around in memory when being linked.

So overall, I'd say that this is a really cool insight and it's great that you're thinking about this, but this by itself is likely not worthwhile from an efficiency perspective.

That being said, there are data structures that do use implicit heaps made of multiple trees that use this same principle. The smoothsort algorithm uses Leonardo heaps, which use a structure similar to but not the same as binomial heaps, and later work introduced the poplar heap which has another similar structure. Weak heaps use an implicit representation not too far off from what you're proposing here.