swift中的优先级队列
我试图实现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)
}
共有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
-
我需要一个优先级队列，它首先获得具有最高优先级值的项目。我当前正在使用队列库中的PriorityQueue类。但是，这个函数只先返回值最小的项。我尝试了一些很难看的解决方案，比如（sys.maxint-priority）作为优先级，但我只是想知道是否存在更优雅的解决方案。
-
我想在Redis中实现一个并发优先级队列，不同机器上的多个进程添加项目（带分数），多个其他进程弹出这些项目，最先得分。 可以使用LPUSH和RPOP实现简单队列。 使用ZSET，我可以使用ZADD添加项目，并使用ZRANGE和ZREM弹出它们，只要只有一个读取器。 对于多个读者，我想我需要像ZPOP这样的东西，它将ZRANGE和ZREM结合在一个原子操作中。否则，两个阅读器可能会在ZREM之前从Z
-
这是我写的Dijkstra算法的代码: 在这方面我不能理解的工作 这涉及到: < code>()运算符在这里有什么用？我是说它在这段代码中是如何运作的？ 还有为什么我们使用
-
我所拥有的是一个类，它创建了一个具有优先级、到达时间和完成时间的对象。我还有许多优先级队列可以将它们放入其中。当我开始时，我将它们放入到达队列中，对它们进行排序，然后查看哪个第一个进入，并将其放入队列中。但是，当我尝试向到达队列添加第二个队列时，它会失败并抛出一个异常。我首先要做的是将所有进程添加到到达队列中，然后对它们进行排序，这样到达时间最短的进程将是到达队列中第一个进入队列的进程。谢谢你帮忙
-
注意：我知道可以用比较器创建优先级队列，然后重复调用Add。
-
考虑下面的优先级类声明<代码>类优先级队列 我的想法： 我能想到的一件事是，这将强制优先级队列使用对象比较器，并且不会提供实现其自定义比较器的能力，因为类的用户可能希望基于某个不同的比较器构建队列。