When to use Binomial Heap?

Question

Binomial Heap has quite special design. Personally I don't think this design is intuitive.

Although posts such as What is the difference between binary heaps and binomial heaps? talks about diff and its speciality, I am still wondering when I should use it.

In http://en.wikipedia.org/wiki/Binomial_heap, it says

Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k−1 trivially by attaching one of them as the leftmost child of root of the other one. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.

I presumes that an advantage of Binomial Heap is its merge. However, Leftist heap also has O(logN) merge and much simpler, why we still use Binomial Heap? When should I use Binomial Heap?

---

edit

One of the actual question I wanna ask here is What's exactly the advantage of Binomial Heap?

Answer 1

The article for the Leftist tree says:

When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete a minimum item, we remove the root and the left and right sub-trees are then merged. Both these operations take O(log n) time. For insertions, this is slower than binomial heaps which support insertion in amortized constant time, O(1) and O(log n) worst-case.

So it appears that the advantage of Binomial heap is that insertions are faster.

At least, that's what asympotitic analysis tells us. Real world running time is something else entirely and, as Gene said in his answer, depends on constant factors. The only way you can determine which is better for your application is to test them.

Answer 2

There is no general answer to your question.

The constant factor in the run time relation to data size for library-level algorithms like this often governs which to choose. For example if an O(1) operation is a factor of 20 times slower than an O(log n) one when n=1, you're better off choosing the O(log n) algorithm for n < 1,000,000.

The conclusion is that asymptotic time bounds are only a guide. You'd use Binomial rather than Leftist heaps if

1. The difference matters in the application. (If it doesn't use the cheapest reliable implementation at hand regardless of algorithm.)
2. BH benchmarks better than LH in the particular application you're building.

Added In response to the OP's comment that he is looking for motivation: I can't speak for this algorithm's author. But in general, algorithm developers live to find novel, beautiful approaches and publish them even if the advantage they provide is marginal or purely theoretical.

This is good. It's how Computer Science progresses. The approach can pay off big in other settings even if there is no big win on the problem at hand.

An (old) example of this is skip lists that were developed in 1989 to solve the same problem with very near the same efficiency as balanced binary search trees, which were known in 1962 or earlier. Why bother? Because we can.

Answer 3

Binomial heaps support the merge operation (destructively merge two heaps) in logarithmic time, whereas it takes linear time with a binary heap.

Answer 4

Binary Heap < Binomial Heap < Fibonacci Heap

This is only with respect to performance. From Wiki,

+------------+---------------+----------+-----------+
| Operation  |    Binary     | Binomial | Fibonacci |
+------------+---------------+----------+-----------+
| Find-min   | Θ(1)          | Θ(1)     | Θ(1)      |
| delete-min | Θ(log n)      | Θ(log n) | O(log n)  |
| insert     | Θ(log n)      | Θ(1)     | Θ(1)      |
| dec-key    | Θ(log n)      | Θ(log n) | Θ(1)      |
| merge      | Θ(m log(n+m)) | O(log n) | Θ(1)      |
+------------+---------------+----------+-----------+