SwiftPriorityQueue
SwiftPriorityQueue是一个纯Swift（无Cocoa）实现的泛型优先队列数据结构，适合在所有支持Swift的平台（macOS、iOS、Linux等）上使用。它具有直观的接口，并且可以与实现Comparable的任何类型配合使用。它通过比较元素之间的顺序而不是使用单独的数字优先级来确定顺序。
内部，SwiftPriorityQueue使用经典二叉堆，从而实现了O(lg n)的入队和出队操作。它包含源代码文档、基于A*算法的示例迷宫解决程序（适用于macOS）以及单元测试（特别是欢迎pull requests以增加更多单元测试）。
功能
- 易于使用的方法接口
- 小型、包裹完整的纯Swift代码库
- 使用O(lg n)的推和弹出操作的经典二叉堆实现
- 可以通过标准的Swift for...in循环进行迭代（实现了
Sequence和IteratorProtocol） - 包含源代码文档
- 有趣的基于A*算法的示例迷宫解决程序
安装
版本1.3.0及以上支持Swift 5。使用版本1.2.1用于Swift 4。使用版本1.1.2用于Swift 3和Swift 2的支持。使用版本1.0用于Swift 1.2的支持。
CocoaPods
使用 CocoaPod 的 SwiftPriorityQueue。
Swift 包管理器（SPM）
将此仓库作为依赖项添加。
手动
将 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。
标准 Swift 协议
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 个元素之后，只有最小的元素被保留（因为顺序是 升序）。所以，最终的优先队列包含元素 0, 1, 3, 4。
娱乐一下 - A*（《astar.swift》）
A* 是一种利用优先队列的寻路算法。附在 SwiftPriorityQueue 中的示例程序是一个使用 A* 的迷宫求解器。如果你想在 《astar.swift》 中重用这个算法，您可以查阅一些源码文档。
版权与许可证
SwiftPriorityQueue 由 David Kopec (@davecom 在 GitHub 上) 编写，并采用 MIT 许可证发布（请参阅 LICENSE）。您可以在我的 GitHub 个人资料页上找到我的联系信息。我鼓励您在此 GitHub 仓库提交拉取请求和报告问题。感谢多年来所有贡献者。