美文网首页
Swift 5.3 —— 优先级队列 Priority Queu

Swift 5.3 —— 优先级队列 Priority Queu

作者: Sunooo | 来源:发表于2021-03-07 23:36 被阅读0次

    优先级队列

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

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

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

    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

    相关文章

      网友评论

          本文标题:Swift 5.3 —— 优先级队列 Priority Queu

          本文链接:https://www.haomeiwen.com/subject/qomkbktx.html