优先级队列
一个优先级队列一般分为两种形式,
最大优先级队列,在前面的元素优先级最高,
最小优先级队列,在前面的元素优先级最低。
优先级队列可以用做堆排序,最短路径算法,哈夫曼编码等。
经常用于找到带有优先级的元素,只需要管理好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
网友评论