algorithm - 持续更新优先级队列的最佳算法/数据结构

Question

我需要经常在不断更新的集合中找到最小值对象。我需要有一个优先队列类型的功能。执行此操作的最佳算法或数据结构是什么？我在考虑有一个排序的树/堆，每次更新对象的值时，我都可以删除该对象，然后将其重新插入到树/堆中。有没有更好的方法来实现这一点？

Answer 1

就简单性而言，二叉堆很难被击败，但它的缺点是 decrease-key 需要 O(n) 的时间。我知道，标准引用资料说它是 O(log n)，但首先你必须找到该项目。这是标准二进制堆的 O(n)。

顺便说一下，如果您决定使用二进制堆，则更改项目的优先级不需要删除并重新插入。您可以就地更改项目的优先级，然后根据需要将其冒泡或筛选。

如果decrease-key 的性能很重要，一个不错的选择是 pairing heap ，这在理论上比斐波纳契堆慢，但更容易实现，并且由于常数因子较低，在实践中比斐波纳契堆更快。在实践中，配对堆优于二叉堆，如果您执行大量减少键操作，则其性能优于二叉堆。

您还可以结合一个二叉堆和一个字典或 HashMap ，并根据元素在堆中的位置更新字典。这会以更多内存和增加其他操作的常数因子为代价，让您更快地减少 key 。