我有兴趣实现一个优先级队列,以实现一个相对简单的高效Astar实现(我的意思是优先级队列很简单).
似乎因为Skip List提供了一个简单的O(1)extract-Min操作和一个O(Log N)的插入操作,它可能与更难实现的具有O(log N)提取的Fibonacci Heap竞争 - 最小和O(1)插入.我认为Skip-List对于具有稀疏节点的图更好,而Fibonacci堆对于具有更密集连接的节点的环境更好.
这可能会使Fibonacci Heap通常更好,但我认为Big-Oh明智的这些是相似的吗？