# 08.优先队列

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

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

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

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

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

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

### 三、 插入元素

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

**步骤1**

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

![1](/files/VtMo5HdA30xa2AN3ssIx)

**步骤2**

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

![2](/files/ohMGNKgfJdKTNNuHSaZr)

**步骤3**

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

![3](/files/kWBOBrA1LLo7Ty3Iw8WD)

**步骤4**

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

![4](/files/JyhU2fKjntzdhkDAqxMd)

**步骤5**

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

![5](/files/AFF9Ct6Gd9yv0yDQs5B2)

**步骤6**

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

![6](/files/mtLXWXwbEZvIHI9niOgt)

**步骤7**

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

![7](/files/g6YoQnENkAaCkKk1bjtI)

#### 插入代码实现

**基础数据结构**

```
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](/files/OvZjuKwShBZhQHxvwKaI)

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/08.-you-xian-dui-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.