我知道dijkstra的算法实际上是用fibonacci堆实现的。但是，它是否也可以使用红黑树实现，并且在最坏情况下运行时间仍然是o（m log n）？
最佳答案
首先，很难看到dijkstra的算法用fibonacci堆实现。尽管fibonacci堆具有很好的渐近性能（o（m+n logn）），但实际上它具有很高的常数因子，因此其他类型的堆更有效。
至于您的问题-是的，您可以使用红黑树作为优先级队列来获得O（m log n）性能这是因为您可以在o（log n）时间内找到红黑树中的最小元素，并在o（logn）时间内通过执行删除和插入来模拟树上的reduce key操作。然而，这可能不如使用标准二进制堆有效，因为红黑树具有更差的引用局部性和更多的内存开销更一般地说，每当您需要优先级队列时，您总是可以使用平衡的二进制搜索树，尽管通常这样做是过分的。
希望这有帮助！