何时使用二项式堆？ [英] When to use Binomial Heap?

问题描述

二项式堆具有非常特殊的设计。个人而言，我不认为这种设计是直观的。

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.

在 http://en.wikipedia.org/wiki/Binomial_heap ，它说

由于其独特的结构，订单k的二项式树可以是由两棵树构成的
通过将
中的一个作为另一个的最左边的孩子来平均地排序k-1。这个特征是
与二叉树堆的合并操作的中心，这是其主要的
优于其他常规堆。

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.

$ b $我假设二项式堆的优点是它的合并。然而， Leftist heap 也有O（logN）合并和更简单，为什么我们仍然使用二项式堆？何时应用二项式堆？

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?

编辑

我想在这里提出的一个实际问题是二项式堆的优点？

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

推荐答案

左派树的文章说：

当将新节点插入到树中时，将创建一个新的单节点树并将其合并到现有树中。要删除最小项，我们删除根，然后合并左右子树。这两个操作都需要O（log n）时间。对于插入，这比二叉式堆栈慢，它支持以分摊的常数时间O（1）和O（log n）最坏情况插入。

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.

至少这是asympotitic分析告诉我们的。现实世界的运行时间是完全不同的，正如基因在答案中所说的，取决于常数因素。您可以确定哪个更适合您的应用程序的唯一方法是测试它们。

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.

这篇关于何时使用二项式堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！