在 RxSwift 框架中，在 PriorityQueue.swift 文件中，使用數(shù)組實現(xiàn)了一個優(yōu)先級隊列 PriorityQueue。

優(yōu)先級隊列（priority queue）是0個或者多個元素的集合，每個元素有一個優(yōu)先級，可以在集合中查找或刪除優(yōu)先級最高的元素。對優(yōu)先級隊列執(zhí)行的操作有:

1. 查找。一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素。
2. 插入一個新元素。
3. 刪除。一般情況下，刪除操作用來刪除優(yōu)先權(quán)最大的元素。
   對于優(yōu)先權(quán)相同的元素，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行。

RxSwift 是通過數(shù)組實現(xiàn)優(yōu)先級隊列的。在有元素入隊列和出隊列的之后必須對數(shù)組中的元素進(jìn)行排序，才能在獲取隊列中優(yōu)先級最高的元素時非?？焖佟xSwift 使用的是最大堆（最小堆）的排序算法，對數(shù)組中的元素進(jìn)行排序的。

堆樹

堆樹（最大堆或者最小堆）的定義如下：

1. 堆樹是一棵完全二叉樹；
2. 堆樹中某個節(jié)點的值總是不大于（或不小于）其子節(jié)點的值；
3. 堆樹中每個節(jié)點的子樹都是堆樹；

當(dāng)父節(jié)點的值總是大于或等于任何一個子節(jié)點的值時為最大堆，當(dāng)父節(jié)點的值總是小于或等于任何一個子節(jié)點的值時為最小堆。

最大堆示例

最小堆示例

構(gòu)造最大樹

怎樣將一個未排序的數(shù)組構(gòu)造成堆樹呢？現(xiàn)在以最大堆為例進(jìn)行講解（最小堆同理）。
加入我們拿到的未排序的數(shù)組為：

var numbers = [6, 2, 5, 4, 20, 13, 14, 15, 9, 7]

數(shù)組對應(yīng)的完全二叉樹如下圖所示：

未排序數(shù)組對應(yīng)的完全二叉樹

如果堆樹中的每個非子節(jié)點的值都大于它的兩個（或一個）相近的子節(jié)點的值，那么整個堆樹就滿足了每個節(jié)點的值總是不小于其子節(jié)點的值。所以構(gòu)造堆樹的基本思路是：首先找到最后一個節(jié)點的父節(jié)點，從這個父節(jié)點開始調(diào)整樹，保證父節(jié)點的值大于子節(jié)點的值。然后從這個父節(jié)點繼續(xù)向前調(diào)整樹，直到所有的非子節(jié)點的值都不小于于它的相鄰的子節(jié)點的值，這樣最大堆就構(gòu)造完畢了。

假設(shè)樹中有n個節(jié)點，從0開始給節(jié)點編號，到n-1結(jié)束，對于編號為i的節(jié)點，其父節(jié)點為(i-1)/2；左子節(jié)點的編號為i2+1，右子節(jié)點的編號為i2+2。最后一個節(jié)點的編號為n-1，其父節(jié)點的編號為(n-2)/2，所有從編號為(n-2)/2的節(jié)點開始調(diào)整樹。

如下圖所示，最后一個節(jié)點為7，其父節(jié)點為20，從20這個節(jié)點開始構(gòu)造最大堆；構(gòu)造完畢之后，轉(zhuǎn)移到下一個父節(jié)點，直到所有父節(jié)點都構(gòu)造完畢。

最大堆構(gòu)造過程1

最大堆構(gòu)造過程2

思路已經(jīng)梳理完成，下面我們看 RxSwift 具體是怎樣實現(xiàn)的。

在PriorityQueue的初始化方法中傳入對比兩個元素優(yōu)先級和判斷元素是否相等的方法。_elements用于保存隊列中的元素。

struct PriorityQueue<Element> {

    private let _hasHigherPriority: (Element, Element) -> Bool
    private let _isEqual: (Element, Element) -> Bool

    fileprivate var _elements = [Element]()

    init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
        _hasHigherPriority = hasHigherPriority
        _isEqual = isEqual
    }
}

獲取優(yōu)先級最高的元素，即返回 _elements 最前的元素：

func peek() -> Element? {
    return _elements.first
}

有元素進(jìn)入隊列時，首先將元素添加到數(shù)組_elements的末尾，相當(dāng)于在堆樹的末尾又添加了一個節(jié)點，這時需要根據(jù)這個節(jié)點的優(yōu)先級和其父節(jié)點的優(yōu)先級調(diào)整數(shù)組。因為在添加元素之前的樹結(jié)構(gòu)已經(jīng)滿足最大堆的要求，所以現(xiàn)在只需要關(guān)注最后一個節(jié)點和它的父節(jié)點的優(yōu)先級，如果最后一個節(jié)點的優(yōu)先級較高，則將最后一個節(jié)點和它的父節(jié)點進(jìn)行調(diào)整。以此類推，一直向上調(diào)整到樹的頂端。

mutating func enqueue(_ element: Element) {
    _elements.append(element)
    bubbleToHigherPriority(_elements.count - 1)
}

// 從下標(biāo)為 initialUnbalancedIndex 處向高的優(yōu)先級處調(diào)整元素
private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
    // 確保 initialUnbalancedIndex 在 _elements 的索引范圍內(nèi)
    precondition(initialUnbalancedIndex >= 0)
    precondition(initialUnbalancedIndex < _elements.count)

    var unbalancedIndex = initialUnbalancedIndex

    while unbalancedIndex > 0 {
        // unbalancedIndex 為未排序的索引
        // parentIndex 為未排序節(jié)點的父節(jié)點的索引
        let parentIndex = (unbalancedIndex - 1) / 2
        guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
        #if swift(>=3.2)
        _elements.swapAt(unbalancedIndex, parentIndex)
        #else
        swap(&_elements[unbalancedIndex], &_elements[parentIndex])
        #endif
        unbalancedIndex = parentIndex
    }
}

將優(yōu)先級最高的元素出隊列，也就是將數(shù)組中的第一個元素移除，同時我們也有可能需要移除數(shù)組中的任意一個的元素。進(jìn)而我們可以將問題歸結(jié)為：怎樣移除指定索引處的元素。

當(dāng)要移除指定索引的元素時，首先將指定索引處的元素和數(shù)組的最后一個元素交換位置，再將最后一個元素移除，這樣原本在數(shù)組最后的元素移到了指定的索引處，這樣有可能破壞了的最大堆的規(guī)則，所以要將指定位置的元素根據(jù)其優(yōu)先級向下浮動，讓它的子節(jié)點中值最大的一個和其交換位置，確保指定索引的優(yōu)先級大于它所有子節(jié)點的優(yōu)先級，然后將指定索引處的元素根據(jù)優(yōu)先級向上浮動，確保指定索引處的元素優(yōu)先級小于或等于其父節(jié)點的優(yōu)先級。代碼如下：

// 優(yōu)先級最高的元素出隊列
mutating func dequeue() -> Element? {
    guard let front = peek() else {
        return nil
    }

    removeAt(0)

    return front
}

// 移除任意一個元素
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 {
        #if swift(>=3.2)
        _elements.swapAt(index, _elements.count - 1)
        #else
        swap(&_elements[index], &_elements[_elements.count - 1])
        #endif
    }

    _ = _elements.popLast()

    if !removingLast {
        bubbleToHigherPriority(index)
        bubbleToLowerPriority(index)
    }
}


// 向低優(yōu)先級冒泡
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 }

        #if swift(>=3.2)
        _elements.swapAt(highestPriorityIndex, unbalancedIndex)
        #else
        swap(&_elements[highestPriorityIndex], &_elements[unbalancedIndex])
        #endif
        unbalancedIndex = highestPriorityIndex
    }
}

到此，RxSwift 的優(yōu)先級隊列 PriorityQueue 的所有功能已經(jīng)實現(xiàn)，它使用最大堆排序，插入和刪除元素的時間復(fù)雜度都是O(log(n))。