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

Question

我有兴趣实现一个优先级队列以启用一个也相对简单的高效 Astar 实现（我的意思是优先级队列很简单）。

似乎因为跳过列表提供了一个简单的 O(1) 提取最小操作和一个 O(Log N) 的插入操作，它可能与更难实现的具有 O(log N) 提取的斐波那契堆竞争 - Min 和 O(1) 插入。我认为 Skip-List 对于节点稀疏的图会更好，而斐波那契堆对于节点更密集的环境会更好。

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

Answer 1

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

Answer 2

斐波那契堆非常非常非常慢，除了非常非常非常大和密集的图（大约数亿条边）。众所周知，它们也很难正确实施。

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

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