# 08.优先队列

### 一、 什么是优先队列

如果有这样一个数据流 `1，2，3，4，5，6，7，8` 我们需要按照一定的优先级找到满足条件（最大或者最小）的元素，并且每次取出最高优先级的元素后，内部元素依旧能够按照既定优先级保证最高优先级的元素在顶端。

### 二、 最大堆 & 最小堆

* `堆` 分为 `最大堆` 和 `最小堆` ，其实就是 `完全二叉树`
  * 最大堆
    * 要求节点的元素都要大于等于其孩子
  * 最小堆
    * 要求节点元素都小于等于其左右孩子
* 两者对左右孩子的大小关系不做任何要求

#### 为什么用 `二叉树` 来实现呢？

如果使用数组复杂度会更高

### 三、 插入元素

如下数据流，我们按照顺序插入数据，并且每次返回最大的元素，我们就可以使用优先队列（最大堆）。

**步骤1**

* 插入 1 和 5 ，如图二叉树结构
* 叶子节点 5 > 1 ，不符合优先级规则，需要交换位置
* 等价数组为
  * \[5, 1]

![1](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-da2cd4cafddbf692f962f44abb4a66421249e912%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-1.png?alt=media)

**步骤2**

* 插入 6
  * 每次插入都插入到当前最深层从左往右的位置，或者创建下一层
* 6 大于父节点 5，需要调整位置
* 交换 5 6
* 等价数组为
  * \[6, 1, 5]

![2](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-53c12570a68203ba3088cf15071800200a752b2a%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-2.png?alt=media)

**步骤3**

* 插入 2
  * 这一层满了，下一层最左边
* 2 大于父节点 1，需要调整
* 交换 2 1
* 等价数组为
  * \[6, 2, 5, 1]

![3](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-d0fa02843b3a7cfc9372c4d64842741707c9fa66%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-3.png?alt=media)

**步骤4**

* 插入 7
* 7 大于父节点 2，需要调整
* 交换 7 2
  * 7 的父节点变为 6，还需要调整
  * 交换 7 6
* 等价数组为
  * \[7, 6, 5, 1, 2]

![4](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-72e717e74d34db17f11b330b6bf27f6cc6647d0b%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-4.png?alt=media)

**步骤5**

* 插入 4，父节点为 5，无需调整
* 等价数组为
  * \[7, 6, 5, 1, 2, 4]

![5](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-7211662dcdf567a9c2464b3dabf9283c1c0ebd53%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-5.png?alt=media)

**步骤6**

* 插入 3，父节点为 5，无需调整
* 等价数组为
  * \[7, 6, 5, 1, 2, 4, 3]

![6](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-967d5ccdd1fe1bebe1b3c61d047fc226d1e44ae6%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-6.png?alt=media)

**步骤7**

* 插入 8
  * 下一层
* 大于父节点 1，交换
* 大于父节点 6，交换
* 大于父节点 7，交换
* 等价数组为
  * \[8, 7, 5, 6, 2, 4, 3, 1]

![7](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-af6ddede53f211efa75f68324b09615d8b6ba978%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-7.png?alt=media)

#### 插入代码实现

**基础数据结构**

```
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
    }
}
```

**插入逻辑**

```
// 插入
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，小于子节点，进行下沉处理

![8](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-851b8ab395a4811a52c186f4e63ba79d073c34bc%2F08.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97-8.png?alt=media)

#### 移除与下沉逻辑实现

```
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
    }
}
```