具有恒定时间增加键操作的最小优先级队列
Min priority queue with constant time increase-key operation
我一直在寻找一种最小堆实现变体，它不是提供分摊的 O(1) 来减少密钥，而是提供 O(1) 来增加它。 （权衡减少键操作的成本为 o(log(n))，因为 here 观察到，这两件事不可能同时进行。
我实际上有一组固定大小的元素，我想对键执行递增，或者用更大的元素替换最小的元素。所以另一种满足这个的方法也很棒！
有人知道具有恒定摊销时间增加键操作的堆变体吗？
谢谢！
我认为您优化得太早了。我建议您启动您的应用程序并 运行 配对堆，然后对其进行概要分析。关于数据以及堆结构将如何执行，您还不知道的事情太多了。
二项式堆、斐波那契堆、配对堆和许多其他变体很难分析，因为它们的行为在很大程度上取决于操作的组合、操作的顺序和数据的性质。例如，在配对堆中，如果节点没有子节点，increase-key 是 O(1)。而节点是否有子节点取决于节点在堆中的位置以及decrease-key或remove-first被调用了多少次。
我怀疑您会找到具有 O(1) 移除和对数插入的堆结构。即使是 Brodal queue，它对于其他所有事情都有 O(1)，对于删除也是 O(log n)。但是请注意，虽然 Brodal 队列是渐进最优的，但用 Brodal 自己的话来说，它是 "quite complicated" 并且“[不] 在实践中实用。”
获取程序 运行。剖析它。然后决定是否需要一个性能更高的优先级队列结构。
实际上你指向的link说的是你不能同时进行的三个操作是O(1) for insert, find-min and increase-key. decrease-key 操作不参与其中。因此，其他操作之一将不得不增加。我怀疑这是可能的。
但是也就是说，斐波那契堆 确实 提供摊销的 随机 O(1) 密钥增加。也就是说，对于一半的元素，您不需要移动它。四分之一，你必须移动它一次。对于 1/8，您必须移动它两次，依此类推。最坏的情况 O(log(n)) 仅在您增加底部元素时才支付。所以增加一个随机元素的平均成本是O(1).
您甚至可以使堆比这更好。当您增加一个元素的值时，您可以将其标记为已增加并使其真正冒泡变得懒惰。除非它到达底部，否则您根本不必移动它。因此，根据使用情况，大多数情况下您根本不需要为搬运东西付费。
我一直在寻找一种最小堆实现变体，它不是提供分摊的 O(1) 来减少密钥，而是提供 O(1) 来增加它。 （权衡减少键操作的成本为 o(log(n))，因为 here 观察到，这两件事不可能同时进行。
我实际上有一组固定大小的元素，我想对键执行递增，或者用更大的元素替换最小的元素。所以另一种满足这个的方法也很棒！
有人知道具有恒定摊销时间增加键操作的堆变体吗？
谢谢！
我认为您优化得太早了。我建议您启动您的应用程序并 运行 配对堆，然后对其进行概要分析。关于数据以及堆结构将如何执行，您还不知道的事情太多了。
二项式堆、斐波那契堆、配对堆和许多其他变体很难分析，因为它们的行为在很大程度上取决于操作的组合、操作的顺序和数据的性质。例如，在配对堆中，如果节点没有子节点，increase-key 是 O(1)。而节点是否有子节点取决于节点在堆中的位置以及decrease-key或remove-first被调用了多少次。
我怀疑您会找到具有 O(1) 移除和对数插入的堆结构。即使是 Brodal queue，它对于其他所有事情都有 O(1)，对于删除也是 O(log n)。但是请注意，虽然 Brodal 队列是渐进最优的，但用 Brodal 自己的话来说，它是 "quite complicated" 并且“[不] 在实践中实用。”
获取程序 运行。剖析它。然后决定是否需要一个性能更高的优先级队列结构。
实际上你指向的link说的是你不能同时进行的三个操作是O(1) for insert, find-min and increase-key. decrease-key 操作不参与其中。因此，其他操作之一将不得不增加。我怀疑这是可能的。
但是也就是说，斐波那契堆 确实 提供摊销的 随机 O(1) 密钥增加。也就是说，对于一半的元素，您不需要移动它。四分之一，你必须移动它一次。对于 1/8，您必须移动它两次，依此类推。最坏的情况 O(log(n)) 仅在您增加底部元素时才支付。所以增加一个随机元素的平均成本是O(1).
您甚至可以使堆比这更好。当您增加一个元素的值时，您可以将其标记为已增加并使其真正冒泡变得懒惰。除非它到达底部，否则您根本不必移动它。因此，根据使用情况，大多数情况下您根本不需要为搬运东西付费。