algorithm – swift中的优先级队列

概述我正在尝试实现Dijkstra算法的一个版本,以找到总线从开始到结束的最短路径.不幸的是,我似乎无法找到一个库或 swift提供一种优先级队列的其他方式,因此我似乎必须编写自己的代码. 话虽这么说,有人能指出我正确的方向吗？ 目前我的想法如下： 写一个将保存优先级数组的类.在这个类中,将有一个接收值的方法,将其添加到优先级数组,然后根据优先级(在这种情况下,距离)对其进行排序.还将有一个get函数 我正在尝试实现Dijkstra算法的一个版本,以找到总线从开始到结束的最短路径.不幸的是,我似乎无法找到一个库或 swift提供一种优先级队列的其他方式,因此我似乎必须编写自己的代码.

话虽这么说,有人能指出我正确的方向吗？

目前我的想法如下：

写一个将保存优先级数组的类.在这个类中,将有一个接收值的方法,将其添加到优先级数组,然后根据优先级(在这种情况下,距离)对其进行排序.还将有一个get函数,它返回数组中最高优先级的项.

我想知道在理解优先级队列时我是否接近或离开了.

谢谢.

编辑：

到目前为止这是我的代码.似乎太短暂和残酷……我必须在概念方面遗漏一些东西.

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[] // get obj associated w/ key 1        var obj2 = self.priorityQueue[] // 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)}

解决方法 看看“heapsort”的代码. Heapsort创建一个“堆”,它基本上是一个具有最大元素的优先级队列,然后它重复d出heap = priority队列的最大元素,将其移动到数组的末尾,并将前一个数组元素添加到优先队列.

插入和删除优先级队列中的项必须是O(log n) *** 作.这是优先队列的重点.在向优先级队列添加元素时调用“排序”是绝对荒谬的,并且会完全扼杀您的性能.

总结

以上是内存溢出为你收集整理的algorithm – swift中的优先级队列全部内容，希望文章能够帮你解决algorithm – swift中的优先级队列所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。