swift中的优先队列

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

应该使用堆排序来确定优先级。我认为这是最理想的!在操场上试试吧!

import Foundation
typealias PriorityDefinition<P> = (_ p1: P, _ p2: P) -> (Bool)
class PriorityQueue<E, P: Hashable> {
    var priDef: PriorityDefinition<P>!
    var elemments = [P: [E]]()
    var priority = [P]()
    init(_ priDef: @escaping PriorityDefinition<P>) {
        self.priDef = priDef
    }
    func enqueue(_ element: E!, _ priorityValue: P!) {
        if let _ = elemments[priorityValue] {
            elemments[priorityValue]!.append(element)
        } else {
            elemments[priorityValue] = [element]
        }
        if !priority.contains(priorityValue) {
            priority.append(priorityValue)
            let lastIndex = priority.count - 1
            siftUp(0, lastIndex, lastIndex)
        }
    }
    func dequeue() -> E? {
        var result: E? = nil
        if priority.count > 0 {
            var p = priority.first!
            if elemments[p]!.count == 1 {
                if priority.count > 1 {
                    let _temp = priority[0]
                    priority[0] = priority[priority.count - 1]
                    priority[priority.count - 1] = _temp
                    p = priority.last!
                    siftDown(0, priority.count - 2)
                }
                result = elemments[p]!.removeFirst()
                elemments[p] = nil
                priority.remove(at: priority.index(of: p)!)
            } else {
                result = elemments[p]!.removeFirst()
            }
        }
        return result
    }
    func siftDown(_ start: Int, _ end: Int) {
        let iLeftChild = 2 * start + 1
        if iLeftChild <= end {
            var largestChild = priDef(priority[iLeftChild], priority[start]) ? iLeftChild : start
            let iRightChild = 2 * start + 2
            if iRightChild <= end {
                if priDef(priority[iRightChild], priority[iLeftChild]) {
                    largestChild = iRightChild
                }
            }
            if largestChild == start {
                return
            } else {
                let _temp = priority[start]
                priority[start] = priority[largestChild]
                priority[largestChild] = _temp
                siftDown(largestChild, end)
            }
        }
    }
    func siftUp(_ start: Int, _ end: Int, _ nodeIndex: Int) {
        let parent = (nodeIndex - 1) / 2
        if parent >= start {
            if priDef(priority[nodeIndex], priority[parent]) {
                let _temp = priority[nodeIndex]
                priority[nodeIndex] = priority[parent]
                priority[parent] = _temp
                siftUp(start, end, parent)
            } else {
                return
            }
        }
    }
    func isEmpty() -> Bool {
        return priority.count == 0
    }
}
let Q = PriorityQueue<Int, Int> { (p1: Int, p2: Int) -> (Bool) in
    return p1 > p2
}
let n = 999
for i in 0...n - 1 {
    let start = NSDate().timeIntervalSince1970
    Q.enqueue(i, i)
    let end = NSDate().timeIntervalSince1970
    print(end - start)
}

Answer 2

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

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

Answer 3

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

你的优先级队列在push上排序的实现是O(n lgn).大多数优先级队列的实现，包括SwiftPriorityQueue，使用二进制堆作为后备存储。它们有在O(lgn)内完成的push操作和在O(lgn)内完成的pop操作。因此，您的怀疑是正确的——您当前的实现不太可能具有很高的性能(尽管pop在技术上更快)。

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

SwiftGraph包含了Dijkstra算法的实现。

我很惊讶这两个项目都不容易找到，因为它们已经问世一年多了，而且还算流行，但根据去年对这个问题的回答，我似乎需要提高可发现性。