「这是我参与2022首次更文挑战的第2天,活动详情查看:2022首次更文挑战」。
👋
我的个人项目 | 扫雷Elic 无尽天梯 | 梦见账本 | 隐私访问记录 |
---|---|---|---|
类型 | 游戏 | 财务 | 工具 |
AppStore | Elic | Umemi | 隐私访问记录 |
一、 什么是优先队列
如果有这样一个数据流 1,2,3,4,5,6,7,8
我们需要按照一定的优先级找到满足条件(最大或者最小)的元素,并且每次取出最高优先级的元素后,内部元素依旧能够按照既定优先级保证最高优先级的元素在顶端。
二、 最大堆 & 最小堆
堆
分为最大堆
和最小堆
,其实就是完全二叉树
- 最大堆
- 要求节点的元素都要大于等于其孩子
- 最小堆
- 要求节点元素都小于等于其左右孩子
- 最大堆
- 两者对左右孩子的大小关系不做任何要求
为什么用 二叉树
来实现呢?
如果使用数组复杂度会更高
三、 插入元素
如下数据流,我们按照顺序插入数据,并且每次返回最大的元素,我们就可以使用优先队列(最大堆)。
步骤1
- 插入 1 和 5 ,如图二叉树结构
- 叶子节点 5 > 1 ,不符合优先级规则,需要交换位置
- 等价数组为
- [5, 1]
步骤2
- 插入 6
- 每次插入都插入到当前最深层从左往右的位置,或者创建下一层
- 6 大于父节点 5,需要调整位置
- 交换 5 6
- 等价数组为
- [6, 1, 5]
步骤3
- 插入 2
- 这一层满了,下一层最左边
- 2 大于父节点 1,需要调整
- 交换 2 1
- 等价数组为
- [6, 2, 5, 1]
步骤4
- 插入 7
- 7 大于父节点 2,需要调整
- 交换 7 2
- 7 的父节点变为 6,还需要调整
- 交换 7 6
- 等价数组为
- [7, 6, 5, 1, 2]
步骤5
- 插入 4,父节点为 5,无需调整
- 等价数组为
- [7, 6, 5, 1, 2, 4]
步骤6
- 插入 3,父节点为 5,无需调整
- 等价数组为
- [7, 6, 5, 1, 2, 4, 3]
步骤7
- 插入 8
- 下一层
- 大于父节点 1,交换
- 大于父节点 6,交换
- 大于父节点 7,交换
- 等价数组为
- [8, 7, 5, 6, 2, 4, 3, 1]
3.1 基础数据结构
public struct SwiftPriorityQueue<Element> {
private let _hasHigherPriority: (Element, Element) -> Bool
private let _isEqual: (Element, Element) -> Bool
private var _elements = [Element]()
public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
_hasHigherPriority = hasHigherPriority
_isEqual = isEqual
}
public func peek() -> Element? {
return _elements.first
}
public func array() -> [Element] {
return _elements
}
public var isEmpty: Bool {
return _elements.count == 0
}
public var count: Int {
return _elements.count
}
}
3.2 插入逻辑
// 插入
public mutating func enqueue(_ element: Element) {
_elements.append(element)
bubbleToHigherPriority(_elements.count - 1)
}
// 爬升
private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
precondition(initialUnbalancedIndex >= 0)
precondition(initialUnbalancedIndex < _elements.count)
var unbalancedIndex = initialUnbalancedIndex
while unbalancedIndex > 0 {
let parentIndex = (unbalancedIndex - 1) / 2
guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
_elements.swapAt(unbalancedIndex, parentIndex)
unbalancedIndex = parentIndex
}
}
四、 移除元素
我们还以上面完成的 优先队列
数据结构为例,继续对移除元素的操作进行研究。
- 这里我们计划移除 5 元素(当前下表为A)
- 现将其和尾部元素交换
- 移除尾部元素
- 检查 A 处元素是否需要爬升
- 是
- 将其上浮
- 此处 A 元素为 1,小于父节点 8,无需处理
- 将其上浮
- 是
- 检查 A 处元素是否需要下沉
- 是
- 将其下降
- 此处 A 元素为 1,小于子节点,进行下沉处理
- 将其下降
- 是
4.1 移除与下沉逻辑实现
private mutating func removeAt(_ index: Int) {
// 是否是最后一个元素
let removingLast = index == _elements.count - 1
if !removingLast {
_elements.swapAt(index, _elements.count - 1)
}
_ = _elements.popLast()
if !removingLast {
// 检查并保持优先队列的元素
bubbleToHigherPriority(index)
bubbleToLowerPriority(index)
}
}
private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
precondition(initialUnbalancedIndex >= 0)
precondition(initialUnbalancedIndex < _elements.count)
var unbalancedIndex = initialUnbalancedIndex
while true {
// 根据二叉树的结构,当前节点左叶子节点的下标为 unbalancedIndex * 2 + 1
let leftChildIndex = unbalancedIndex * 2 + 1
// 根据二叉树的结构,当前节点右叶子节点的的下标为 unbalancedIndex * 2 + 2
let rightChildIndex = unbalancedIndex * 2 + 2
var highestPriorityIndex = unbalancedIndex
// 左叶子更高
if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
highestPriorityIndex = leftChildIndex
}
// 右叶子更高
if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
highestPriorityIndex = rightChildIndex
}
guard highestPriorityIndex != unbalancedIndex else {
break // 不用调整优先级
}
// 交换元素
_elements.swapAt(highestPriorityIndex, unbalancedIndex)
// 保存更高优先级的下标,继续进行对比
unbalancedIndex = highestPriorityIndex
}
}
五、 Swift 完整实现
下面的优先队列实现是参考 RxSwift 中的
public struct SwiftPriorityQueue<Element> {
private let _hasHigherPriority: (Element, Element) -> Bool
private let _isEqual: (Element, Element) -> Bool
private var _elements = [Element]()
public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
_hasHigherPriority = hasHigherPriority
_isEqual = isEqual
}
public mutating func enqueue(_ element: Element) {
_elements.append(element)
bubbleToHigherPriority(_elements.count - 1)
}
public func peek() -> Element? {
return _elements.first
}
public func array() -> [Element] {
return _elements
}
public var isEmpty: Bool {
return _elements.count == 0
}
public var count: Int {
return _elements.count
}
public mutating func dequeue() -> Element? {
guard let front = peek() else {
return nil
}
removeAt(0)
return front
}
public mutating func remove(_ element: Element) {
for i in 0 ..< _elements.count {
if _isEqual(_elements[i], element) {
removeAt(i)
return
}
}
}
private mutating func removeAt(_ index: Int) {
let removingLast = index == _elements.count - 1
if !removingLast {
_elements.swapAt(index, _elements.count - 1)
}
_ = _elements.popLast()
if !removingLast {
bubbleToHigherPriority(index)
bubbleToLowerPriority(index)
}
}
private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
precondition(initialUnbalancedIndex >= 0)
precondition(initialUnbalancedIndex < _elements.count)
var unbalancedIndex = initialUnbalancedIndex
while unbalancedIndex > 0 {
let parentIndex = (unbalancedIndex - 1) / 2
guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
_elements.swapAt(unbalancedIndex, parentIndex)
unbalancedIndex = parentIndex
}
}
private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
precondition(initialUnbalancedIndex >= 0)
precondition(initialUnbalancedIndex < _elements.count)
var unbalancedIndex = initialUnbalancedIndex
while true {
let leftChildIndex = unbalancedIndex * 2 + 1
let rightChildIndex = unbalancedIndex * 2 + 2
var highestPriorityIndex = unbalancedIndex
if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
highestPriorityIndex = leftChildIndex
}
if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
highestPriorityIndex = rightChildIndex
}
guard highestPriorityIndex != unbalancedIndex else { break }
_elements.swapAt(highestPriorityIndex, unbalancedIndex)
unbalancedIndex = highestPriorityIndex
}
}
}
extension SwiftPriorityQueue : CustomDebugStringConvertible {
public var debugDescription: String {
return _elements.debugDescription
}
}
今天的文章Swift-图解优先队列实现分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/13550.html