algorithm – swift中的优先级队列
发布时间:2020-12-14 04:54:07 所属栏目:百科 来源:网络整理
导读:我正在尝试实现Dijkstra算法的一个版本,以找到总线从开始到结束的最短路径.不幸的是,我似乎无法找到一个库或 swift提供一种优先级队列的其他方式,因此我似乎必须编写自己的代码. 话虽这么说,有人能指出我正确的方向吗? 目前我的想法如下: 写一个将保存优先
我正在尝试实现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[$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) } 解决方法
看看“heapsort”的代码. Heapsort创建一个“堆”,它基本上是一个具有最大元素的优先级队列,然后它重复弹出heap = priority队列的最大元素,将其移动到数组的末尾,并将前一个数组元素添加到优先队列.
插入和删除优先级队列中的项必须是O(log n)操作.这是优先队列的重点.在向优先级队列添加元素时调用“排序”是绝对荒谬的,并且会完全扼杀您的性能. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |