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?

score 8 · Accepted Answer · answered Nov 20 '13 at 16:11

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.

Downvoter? Something you want to share? It's customary to provide a reason for the downvote. — Jim Mischel, Nov 20 '13 at 22:08

Gene · Answer 2 · 2013-11-21T18:59:32.400

6

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

The difference matters in the application. (If it doesn't use the cheapest reliable implementation at hand regardless of algorithm.)
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.

edited Nov 21 '13 at 18:59

answered Nov 20 '13 at 14:38

Gene

46,253
4
58
96

What's exactly the advantage of Binomial Heap? – Jackson Tale Nov 20 '13 at 15:05
@JacksonTale as I said, there is no general answer. When you benchmark it, it might perform better than other algorithms due to constant factors of execution of certain ops. My guess is that its merge operation will have less overhead than the LH merge. But you must benchmark it to find out. Complex does not mean slow. – Gene Nov 20 '13 at 18:22
1

I guess the answer OP's asking is more directed towards, "What motivated someone to design Binomial Heap?". Because he said the design is "not intuitive", so he must be wondering why it was constructed in the first place, and he thought that there must be a particular use for it. – justhalf Nov 21 '13 at 07:07
@justhalf yes. I just wish for a motivation. – Jackson Tale Nov 21 '13 at 15:38
@JacksonTale See addition to answer above. – Gene Nov 21 '13 at 17:14

score 5 · Answer 3 · answered Nov 20 '13 at 21:53

5

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

answered Nov 20 '13 at 21:53

heap

51
1

linear time or nlogn in binary heap? – Jackson Tale Nov 21 '13 at 17:13
@JacksonTale- That operation takes O(n) time in a binary heap because you can use the heapify operation to build a new heap from the two existing heaps in linear time. – templatetypedef Nov 21 '13 at 17:17

score 1 · Answer 4 · edited Mar 16 '15 at 10:12

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

When to use Binomial Heap?

4 Answers4

Linked