use*_*383 7 algorithm heap priority-queue skip-lists fibonacci-heap
我有兴趣实现一个优先级队列,以实现一个相对简单的高效Astar实现(我的意思是优先级队列很简单).
似乎因为Skip List提供了一个简单的O(1)extract-Min操作和一个O(Log N)的插入操作,它可能与更难实现的具有O(log N)提取的Fibonacci Heap竞争 - 最小和O(1)插入.我认为Skip-List对于具有稀疏节点的图更好,而Fibonacci堆对于具有更密集连接的节点的环境更好.
这可能会使Fibonacci Heap通常更好,但我认为Big-Oh明智的这些是相似的吗？
Fibonacci堆的存在理由是O(1)减少键操作,使得Dijkstra算法能够在时间O(| V | log | V | + | E |)中运行.但实际上,如果我需要一个有效的减少键操作,我会使用一个配对堆,因为Fibonacci堆有很糟糕的常量.如果你的键是小整数,那么使用箱子可能更好.
斐波那契堆非常非常非常慢，除了非常非常非常大和密集的图（大约数亿条边）。众所周知，它们也很难正确实施。
另一方面，跳跃列表是非常好的数据结构，并且实现起来相对简单。
但是我想知道为什么您不考虑使用简单的二进制堆。我相信基于二进制堆的优先级队列甚至比基于跳过列表的优先级队列更快。跳过列表主要用于利用并发性。