优先级队列-跳过列表与斐波那契堆

Question

我感兴趣的是实现优先级队列，以实现高效的Astar实现，同时也相对简单(我的意思是优先级队列很简单)。

似乎因为Skip List提供了一个简单的O(1) extract-Min操作和一个O(Log )的insert操作，所以它可能会与更难实现的Fibonacci Heap竞争，后者具有O(log ) extract-Min和O(1) insert。我认为Skip-List对于具有稀疏节点的图更好，而Fibonacci堆对于具有更密集连接的节点的环境将更好。

这可能会使斐波那契堆通常更好，但我假设大-哦明智的这些将是相似的，这是正确的吗？

Answer 1

Fibonacci堆的理由是O(1)减键操作，使Dijkstra的算法在O(|V| log |V| + |E|)时间内运行。然而，在实践中，如果我需要一个有效的减键操作，我会使用配对堆，因为斐波那契堆有糟糕的常量。如果您的密钥是小整数，那么使用bin可能会更好。

Answer 2

Fibonacci堆非常慢，除了非常大和密集的图(数亿条边的数量级)。它们也是出了名的难以正确实现。

另一方面，跳过列表是非常好的数据结构，实现起来也相对简单。

但是，我想知道您为什么不考虑使用简单的二进制堆。我相信基于二进制堆的优先级队列比基于跳过列表的优先级队列更快。跳过列表主要用于利用并发性。