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

Question

我有兴趣实现一个优先级队列来启用一个高效的 Astar 实现，它也相对简单(我的意思是优先级队列很简单)。

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

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

Answer 1

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