Swift-图解优先队列实现-六虎

「这是我参加2022首次更文挑战的第2天，活动概况查看：2022首次更文挑战」。

Wechat: RyukieW
技术文章归档
Github

我的个人项目	扫雷Elic 无尽天梯	梦见账本	隐私访问记载
类型	游戏	财政	工具
AppStore	Elic	Umemi	隐私访问记载

更多专栏：

Lawliet的独立开发碎碎念

Lawliet的iOS游园会

Lawliet的iOS底层实验室

Lawliet的iOS逆向实验室

Lawliet的刷题小本本

Lawliet的Flutter实验室

一、什么是优先行列

假如有这样一个数据流 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-图解优先队列实现

一、 什么是优先行列

二、 最大堆 & 最小堆

为什么用 二叉树 来完成呢？

三、 刺进元素

3.1 基础数据结构

3.2 刺进逻辑

四、 移除元素

4.1 移除与下沉逻辑完成

五、 Swift 完好完成

相关文章

(七)Java网络编程-IO模型篇之从BIO、NIO、AIO到内核select、epoll剖析！

Swift 最佳实践之 Closure

2022年终总结——从逆向转向Web开发

Redis 底层数据结构大揭秘：五张图看透Redis数据结构

作者信息

一、什么是优先行列

二、最大堆 & 最小堆

为什么用 `二叉树` 来完成呢？

三、刺进元素

四、移除元素