具有恒定时间递增密钥操作的最小优先级队列

我认为你优化得太早了。我建议您启动应用程序并使用配对堆运行,然后对其进行分析。关于数据和堆结构将如何执行,有太多事情您还不知道。

二项式堆、斐波那契堆、配对堆和许多其他变量都很难分析,因为它们的行为在很大程度上取决于操作的组合、操作的顺序和数据的性质。例如,在配对堆中, 增加键 如果节点没有子节点,则为o(1)。节点是否有子节点取决于节点在堆中的位置和多少次 减少键 或 先删除 已经被叫来了。

我怀疑您会找到一个具有o(1)删除和对数插入的堆结构。甚至 Brodal queue ,对于其他所有内容都有o(1),对于删除则是o(log n)。然而,请注意,尽管brodal队列是渐近最优的,但用brodal自己的话说,它“相当复杂”并且“在实践中不实用”。

运行你的程序。分析一下。然后决定是否需要更高性能的优先级队列结构。

实际上,你所指的链接表明,三个不能同时进行的操作是 O(1) 对于 insert 我是说, find-min 和 increase-key 是的。这个 decrease-key 手术不算进去。所以其他的行动之一将不得不增加。我怀疑这是可能的。

但也就是说,斐波那契堆 做 分期付款要约 随机的 O(一) 关键增长。也就是说,对于一半的元素,你不需要移动它。四分之一的时间你必须移动一次。对于1/8你必须移动它两次,以此类推。最坏的情况 O(log(n)) 仅当增加底部元素时才支付。所以增加一个随机元素的平均成本是 O(一) 是的。

你甚至可以做得更好。当您增加一个元素的值时,您可以将其标记为已增加,并使它实际上冒泡是懒惰的。除非它到达底部,你根本不需要移动它。所以,根据使用情况,大多数时候你根本不用为搬家付钱。