在 RxSwift 框架中，在 PriorityQueue.swift 文件中权谁，使用數(shù)組實(shí)現(xiàn)了一個優(yōu)先級隊列 PriorityQueue。
優(yōu)先級隊列（priority queue）是0個或者多個元素的集合憋沿，每個元素有一個優(yōu)先級旺芽，可以在集合中查找或刪除優(yōu)先級最高的元素。對優(yōu)先級隊列執(zhí)行的操作有:
- 查找辐啄。一般情況下采章，查找操作用來搜索優(yōu)先權(quán)最大的元素。
- 插入一個新元素壶辜。
- 刪除悯舟。一般情況下，刪除操作用來刪除優(yōu)先權(quán)最大的元素砸民。
對于優(yōu)先權(quán)相同的元素抵怎，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行。
RxSwift 是通過數(shù)組實(shí)現(xiàn)優(yōu)先級隊列的岭参。在有元素入隊列和出隊列的之后必須對數(shù)組中的元素進(jìn)行排序便贵，才能在獲取隊列中優(yōu)先級最高的元素時非常快速冗荸。RxSwift 使用的是最大堆（最小堆）的排序算法，對數(shù)組中的元素進(jìn)行排序的利耍。
堆樹
堆樹（最大堆或者最小堆）的定義如下：
- 堆樹是一棵完全二叉樹蚌本；
- 堆樹中某個節(jié)點(diǎn)的值總是不大于（或不小于）其子節(jié)點(diǎn)的值盔粹；
- 堆樹中每個節(jié)點(diǎn)的子樹都是堆樹；
當(dāng)父節(jié)點(diǎn)的值總是大于或等于任何一個子節(jié)點(diǎn)的值時為最大堆程癌，當(dāng)父節(jié)點(diǎn)的值總是小于或等于任何一個子節(jié)點(diǎn)的值時為最小堆舷嗡。
構(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)的完全二叉樹如下圖所示：
如果堆樹中的每個非子節(jié)點(diǎn)的值都大于它的兩個（或一個）相近的子節(jié)點(diǎn)的值进萄，那么整個堆樹就滿足了每個節(jié)點(diǎn)的值總是不小于其子節(jié)點(diǎn)的值。所以構(gòu)造堆樹的基本思路是：首先找到最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)锐峭，從這個父節(jié)點(diǎn)開始調(diào)整樹中鼠，保證父節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值。然后從這個父節(jié)點(diǎn)繼續(xù)向前調(diào)整樹沿癞，直到所有的非子節(jié)點(diǎn)的值都不小于于它的相鄰的子節(jié)點(diǎn)的值援雇，這樣最大堆就構(gòu)造完畢了。
假設(shè)樹中有n個節(jié)點(diǎn)椎扬，從0開始給節(jié)點(diǎn)編號惫搏，到n-1結(jié)束，對于編號為i的節(jié)點(diǎn)蚕涤，其父節(jié)點(diǎn)為(i-1)/2筐赔；左子節(jié)點(diǎn)的編號為i2+1，右子節(jié)點(diǎn)的編號為i2+2揖铜。最后一個節(jié)點(diǎn)的編號為n-1茴丰，其父節(jié)點(diǎn)的編號為(n-2)/2，所有從編號為(n-2)/2的節(jié)點(diǎn)開始調(diào)整樹蛮位。
如下圖所示较沪，最后一個節(jié)點(diǎn)為7，其父節(jié)點(diǎn)為20失仁，從20這個節(jié)點(diǎn)開始構(gòu)造最大堆尸曼；構(gòu)造完畢之后晋柱，轉(zhuǎn)移到下一個父節(jié)點(diǎn)借浊，直到所有父節(jié)點(diǎn)都構(gòu)造完畢薄湿。
思路已經(jīng)梳理完成蜓竹，下面我們看 RxSwift 具體是怎樣實(shí)現(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é)點(diǎn)，這時需要根據(jù)這個節(jié)點(diǎn)的優(yōu)先級和其父節(jié)點(diǎn)的優(yōu)先級調(diào)整數(shù)組萧恕。因為在添加元素之前的樹結(jié)構(gòu)已經(jīng)滿足最大堆的要求刚梭，所以現(xiàn)在只需要關(guān)注最后一個節(jié)點(diǎn)和它的父節(jié)點(diǎn)的優(yōu)先級肠阱，如果最后一個節(jié)點(diǎn)的優(yōu)先級較高，則將最后一個節(jié)點(diǎn)和它的父節(jié)點(diǎn)進(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é)點(diǎn)的父節(jié)點(diǎn)的索引
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é)點(diǎn)中值最大的一個和其交換位置肆糕，確保指定索引的優(yōu)先級大于它所有子節(jié)點(diǎn)的優(yōu)先級，然后將指定索引處的元素根據(jù)優(yōu)先級向上浮動在孝，確保指定索引處的元素優(yōu)先級小于或等于其父節(jié)點(diǎn)的優(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)實(shí)現(xiàn)私沮，它使用最大堆排序始赎，插入和刪除元素的時間復(fù)雜度都是O(log(n))。
