优先队列迅速

Question

我正在尝试实现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)
}

Answer 1

查看“堆排序”的代码。Heapsort 创建一个“堆”，它基本上是一个优先级队列，首先具有最大的元素，然后它重复弹出堆 = 优先级队列中的最大元素，将其移动到数组的末尾，并将之前的最后一个数组元素添加到优先级队列。

在优先级队列中插入和删除项目必须是 O (log n) 操作。这就是优先级队列的全部意义。在将元素添加到优先级队列时调用“sort”绝对是荒谬的，并且会完全破坏你的性能。