优先级队列 - 跳过列表与斐波那契堆
我有兴趣实现一个优先级队列，以实现一个高效的 Astar 实现，该实现也相对简单（我的意思是优先级队列很简单）。
看起来，因为跳过列表提供了一个简单的 O(1) 提取最小操作和一个 O(Log N) 的插入操作，所以它可能与更难实现 O(log N) 提取的斐波那契堆竞争。最小和 O(1) 插入。我认为跳过列表更适合具有稀疏节点的图，而斐波那契堆更适合具有更密集连接节点的环境。
这可能会使斐波那契堆通常更好，但我是否正确地假设这些会相似？
I am interested in implementing a priority queue to enable an efficient Astar implementation that is also relatively simple (the priority queue is simple I mean).
It seems that because a Skip List offers a simple O(1) extract-Min operation and an insert operation that is O(Log N) it may be competitive with the more difficult to implement Fibonacci Heap which has O(log N) extract-Min and an O(1) insert. I suppose that the Skip-List would be better for a graph with sparse nodes whereas a Fibonacci heap would be better for an environment with more densely connected nodes.
This would probably make the Fibonacci Heap usually better, but am I correct in assuming that Big-Oh wise these would be similar?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
斐波那契堆存在的理由是 O(1) 递减键操作，使 Dijkstra 算法能够在 O(|V| log |V| + |E|) 时间内运行。然而，在实践中，如果我需要有效的减少键操作，我会使用配对堆，因为斐波那契堆的常数很糟糕。如果您的键是小整数，那么使用 bin 可能会更好。
The raison d'etre of the Fibonacci heap is the O(1) decrease-key operation, enabling Dijkstra's algorithm to run in time O(|V| log |V| + |E|). In practice, however, if I needed an efficient decrease-key operation, I'd use a pairing heap, since the Fibonacci heap has awful constants. If your keys are small integers, it may be even better just to use bins.
斐波那契堆非常非常非常慢，除了非常非常非常大和密集的图（大约数亿条边）。众所周知，它们也很难正确实施。
另一方面，跳跃列表是非常好的数据结构，并且实现起来相对简单。
但是我想知道为什么您不考虑使用简单的二进制堆。我相信基于二进制堆的优先级队列甚至比基于跳过列表的优先级队列更快。跳过列表主要用于利用并发性。
Fibonacci heaps are very very very slow except for very very very very large and dense graphs (on the order of hundreds of millions of edges). They are also notoriously difficult to implement correctly.
On the other hand, skip lists are very nice data structures and relatively simple to implement.
However I wonder why you're not considering using a simple binary heap. I believe binary heaps-based priority queues are even faster than skip list-based priority queues. Skip lists are mainly used to take advantage of concurrency.