SwiftPriorityQueue 是一个纯 Swift (无 Cocoa) 实现的通用优先级队列数据结构，适用于所有支持 Swift 的平台（macOS、iOS、Linux 等）。它具有直观的接口，可以与任何实现了 Comparable 协议的类型一起使用。它使用元素之间的比较，而不是单独的数字优先级来确定顺序。
在内部，SwiftPriorityQueue 使用经典的二叉堆，从而实现 O(lg n) 的入队和出队操作。它包含源代码文档、一个基于 A* 算法的示例迷宫求解程序（适用于 macOS）和单元测试（特别欢迎提交更多单元测试的 pull request）。
- 易于使用的方法接口
- 小型、自包含、纯 Swift 代码库
- 经典二叉堆实现，具有 O(lg n) 的入队和出队操作
- 可通过标准 Swift for...in 循环进行迭代 (实现了
Sequence和IteratorProtocol) - 源代码文档
- 一个有趣的基于 A* 算法的迷宫求解示例程序
1.3.0 及以上版本支持 Swift 5。Swift 4 请使用 1.2.1 版本。Swift 3 和 Swift 2 请使用 1.1.2 版本。Swift 1.2 请使用 1.0 版本。
使用 CocoaPod SwiftPriorityQueue。
将此仓库添加为依赖项。
将 SwiftPriorityQueue.swift 复制到您的项目中。
源代码中有大量使用标准 Swift 文档技术（与 Jazzy 兼容）的文档。 但本质上，SwiftPriorityQueue 具有您期望的三个关键方法 - push()、pop() 和 peek()。
创建新的 PriorityQueue 时，您可以选择指定优先级队列是升序还是降序。 这意味着什么？ 如果优先级队列是升序的，则其最小值（由其 Comparable 实现，即 < 确定）将首先被弹出，如果是降序的，则其最大值将首先被弹出。
var pq: PriorityQueue<String> = PriorityQueue<String>(ascending: true)
您还可以提供一个起始值数组，以便将其按顺序立即推入优先级队列。
var pq: PriorityQueue<Int> = PriorityQueue<Int>(startingValues: [6, 2, 3, 235, 4, 500])
或者您可以同时指定两者。
var pq: PriorityQueue<Int> = PriorityQueue<Int>(ascending: false, startingValues: [6, 2, 3, 235, 4, 500])
或者您可以两者都不指定。 默认情况下，PriorityQueue 是降序且为空的。 您可能已经注意到，PriorityQueue 采用泛型类型。 此类型必须是 Comparable，因为它的比较将用于确定优先级。 这意味着您的自定义类型必须实现 Comparable 并利用重写的 < 来确定优先级。
PriorityQueue 具有您期望优先级队列数据结构具有的所有标准方法。
push(element: T)- 将一个元素放入优先级队列。 O(lg n)push(element: T, maxCount: Int) -> T?- 添加一个元素，同时将优先级队列的大小限制为maxCount。 如果在添加后优先级队列中的元素多于maxCount，则优先级最低的元素将被丢弃并返回。 请注意，这是低效的，因为这是一个二叉堆，因此只有优先级最高的项目才能有效检索。 O(n)pop() -> T?- 返回并删除具有最高（如果升序则为最低）优先级的元素，如果优先级队列为空，则返回nil。 O(lg n)peek() -> T?- 返回具有最高（如果升序则为最低）优先级的元素，如果优先级队列为空，则返回nil。 O(1)clear()- 从优先级队列中删除所有元素。remove(item: T)- 删除优先级队列中首次找到的 item 实例。 如果未找到，则静默返回。 O(n)removeAll(item: T)- 通过重复调用remove()来删除优先级队列中 item 的所有实例。 如果未找到，则静默返回。
count: Int- 优先级队列中的元素数。isEmpty: Bool- 如果优先级队列中没有元素，则为true，否则为false。
PriorityQueue 实现了 IteratorProtocol、Sequence 和 Collection，因此您可以将 PriorityQueue 视为任何其他 Swift 序列/集合。 这意味着您可以在 PriorityQueue 上使用 Swift 标准库函数，并像这样迭代 PriorityQueue
for item in pq { // pq is a PriorityQueue<String>
print(item)
}
这样做时，PriorityQueue 中的每个项目都会按顺序弹出。 PriorityQueue 还实现了 CustomStringConvertible 和 CustomDebugStringConvertible。
print(pq)
注意：PriorityQueue 是非线程安全的（不要同时从多个线程操作它）。
假设您只想在优先级队列中保留 maxCount 个优先级最高的项目。
例如，假设您只希望优先级队列永远只有 4 个元素
var pq: PriorityQueue<Int> = PriorityQueue<Int>()
let maxCount = 4
pq.push(4, maxCount: maxCount)
pq.push(5, maxCount: maxCount)
pq.push(0, maxCount: maxCount)
pq.push(3, maxCount: maxCount)
pq.push(6, maxCount: maxCount)
pq.push(1, maxCount: maxCount)
在这种情况下，在推送了 4 个元素后，只保留了最小的元素（因为顺序是 ascending）。 因此，最终的优先级队列包含元素 0、1、3、4。
A* 是一种使用优先级队列的寻路算法。 SwiftPriorityQueue 附带的示例程序是一个使用 A* 的迷宫求解器。 如果您想在 astar.swift 中重用此算法，可以找到一些源代码文档。
SwiftPriorityQueue 由 David Kopec (@davecom on GitHub) 编写，并根据 MIT 许可证发布（请参阅 LICENSE）。 您可以在我的 GitHub 个人资料页面上找到我的联系方式。 我鼓励您提交 pull request 并在 GitHub 上提出 issue。 感谢多年来的所有贡献者。