swift中的优先级队列

Question

我试图实现Dijkstra算法的一个版本，以找到公共汽车从起点到终点的最短路线。不幸的是，我似乎找不到swift提供优先级队列类型的库或其他方式，所以我似乎必须自己编写代码。

话虽如此，有人能指出我做这件事的正确方向吗？

目前我的想法如下：

到目前为止这是我的代码。似乎太短太残忍了...我一定是在概念上漏掉了什么。

var priorityQueue = Dictionary<String, Int>()
var firstElement: String = ""

func push(name: String, distance: Int)
{
    priorityQueue[name] = distance
    var myArr = Array(priorityQueue.keys)
    var sortedKeys = sort(myArr) {
        var obj1 = self.priorityQueue[$0] // get obj associated w/ key 1
        var obj2 = self.priorityQueue[$1] // get obj associated w/ key 2
        return obj1 > obj2
    }

    firstElement = myArr[0]
    var tempPriorityQueue = Dictionary<String, Int>()
    for val in myArr
    {
        tempPriorityQueue[val] = priorityQueue[val]
    }

    priorityQueue = tempPriorityQueue
}

func pop() -> String
{
    priorityQueue.removeValueForKey(firstElement)
}

Answer 1

您可能会对我编写的两个开源项目感兴趣。第一个是SwiftPriorityQueue：https://github.com/davecom/SwiftPriorityQueue

您的优先级队列的实现在推送上排序，这是O(n，lg，n)。大多数优先级队列的实现，包括SwiftPriorityQueue，都使用二进制堆作为后备存储。它们有在O（lg n）中操作的push操作和在O（lg n）中操作的pops操作。因此，您的怀疑是正确的--您当前的实现不太可能很好（尽管POP在技术上更快）。

第二个是SwiftGraph：https://github.com/davecom/swiftGraph