何时使用二项式堆？

Question

Binomial Heap有很特别的设计.我个人认为这种设计不直观.

虽然帖子如二进制堆和二项式堆有什么区别？谈论差异及其专长,我仍然想知道何时应该使用它.

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

由于其独特的结构,可以通过将其中一个树作为另一个树的根最左边的子项,从k-1的两个树中简单地构造k阶二叉树.此功能是二项式堆合并操作的核心,这是其优于其他传统堆的主要优势.

我认为二项式堆的优势在于它的合并.但是,Leftist heap还有O(logN)合并更简单,为什么我们仍然使用二项式堆？我什么时候应该使用二项式堆？

---

编辑

我想问的一个实际问题是二项式堆的优势究竟是什么？

Answer 1

二项式堆支持对数时间的合并操作（破坏性地合并两个堆），而二项式堆则需要线性时间。

Answer 2

你的问题没有一般的答案.

像这样的库级算法的运行时关系与数据大小的常数因素通常决定了选择哪个.例如,如果在n = 1时O(1)运算比O(log n)运算慢20倍,那么最好选择n <1,000,000的O(log n)算法.

结论是渐近时间界限只是一个指导.如果你使用二项式而不是左撇子堆

1. 差异在申请中很重要.(如果它不使用最便宜的可靠实现,无论算法如何.)
2. 在您正在构建的特定应用程序中,BH基准测试优于LH.

添加 为了回应OP的评论他正在寻找动机:我不能代表这个算法的作者.但总的来说,即使算法开发人员提供的优势是边缘的或纯粹的理论,算法开发人员仍然可以找到新颖,美观的方法并发布它们.

这很好.这就是计算机科学的发展方向.即使手头的问题没有大的胜利,这种方法也可以在其他环境中获得巨大回报.

这个(旧的)例子是1989年开发的跳过列表,用于解决同样的问题,其效率与平衡二叉搜索树非常接近,后者在1962年或更早时就已知.何必？因为我们可以.

Answer 3

左派树的文章说:

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

所以看来二项堆的优点是插入更快.

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