Swift 5.3 —— 优先级队列 Priority Queu

优先级队列

一个优先级队列一般分为两种形式，
最大优先级队列，在前面的元素优先级最高，
最小优先级队列，在前面的元素优先级最低。

优先级队列可以用做堆排序，最短路径算法，哈夫曼编码等。
经常用于找到带有优先级的元素，只需要管理好enqueue和dequeue即可

优先级队列是队列的一种，因此他也符合队列协议
构造优先级队列的方式有很多种

1.使用堆结构

struct PriorityQueue<Element: Equatable>: Queue {
    @discardableResult
    mutating func enqueue(_ element: Element) -> Bool {
        heap.insert(element)
        return true
    }
    
    @discardableResult
    mutating func dequeue() -> Element? {
        heap.remove()
    }
    
    var isEmpty: Bool {
        heap.isEmpty
    }
    
    var peek: Element? {
        heap.peek()
    }
    
    private var heap: Heap<Element>
    
    init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) {
        heap = Heap(sort: sort, elements: elements)
    }
}

2.使用数组

public struct PriorityQueueArray<Element: Equatable>: Queue {
    @discardableResult
    public mutating func enqueue(_ element: Element) -> Bool {
        for (index, otherElement) in elements.enumerated() {
            if sort(element, otherElement) {
                elements.insert(element, at: index)
                return true
            }
        }
        elements.append(element)
        return true
    }
    
    @discardableResult
    public mutating func dequeue() -> Element? {
        isEmpty ? nil : elements.removeFirst()
    }
    
    public var isEmpty: Bool {
        elements.isEmpty
    }
    
    public var peek: Element? {
        elements.first
    }
    
    private var elements: [Element] = []
    let sort: (Element, Element) -> Bool
    
    public init(sort: @escaping (Element, Element) -> Bool, elements: [Element]) {
        self.elements = elements
        self.sort = sort
        self.elements.sort(by: sort)
        
    }
    
}

github仓库地址 https://github.com/SunZhiC/DataStructuresInSwift

References

Data Structures & Algorithms in Swift by Matthijs Hollemans.
https://github.com/apple/swift-algorithms
https://github.com/raywenderlich/swift-algorithm-club