In the RxSwift framework, in the priorityqueue. swift file, a PriorityQueue PriorityQueue is implemented using arrays.

A priority queue is a collection of zero or more elements, each of which has a priority. The element with the highest priority can be found or deleted from the collection. The operations performed on the priority queue are:

  1. Lookup. In general, the lookup operation is used to search for the element with the highest priority.
  2. Insert a new element.
  3. Delete it. Normally, the delete operation is used to remove the element with the highest priority. Elements with the same priority can be processed in first-in, first-out order or with any priority.

RxSwift implements priority queues through arrays. The elements in the array must be sorted after the elements are enqueued and dequeued, so it is very fast to get the highest priority element in the queue. RxSwift uses the maximum heap (minimum heap) sorting algorithm to sort the elements of an array.

Heap tree

A heap tree (maximum heap or minimum heap) is defined as follows:

  1. The heap tree is a complete binary tree;
  2. The value of a node in the heap tree is always no greater than (or less than) the value of its children;
  3. The subtree of each node in a heap tree is a heap tree;

The maximum heap is when the value of the parent node is always greater than or equal to the value of any of the children, and the minimum heap is when the value of the parent node is always less than or equal to the value of any of the children.

Structural maximum tree

How do you construct a heaps tree from an unsorted array? Now use the maximum heap as an example (same with the minimum heap). Add the unsorted array we have:

var numbers = [6.2.5.4.20.13.14.15.9.7]
Copy the code

The complete binary tree corresponding to the array is shown in the figure below:

If the value of each non-child node in the heap tree is greater than the value of its two (or one) close children, then the whole heap tree is such that the value of each node is always no less than the value of its children. Therefore, the basic idea of constructing a heap tree is to find the parent node of the last node and adjust the tree from the parent node to ensure that the value of the parent node is greater than the value of the child node. The tree is then adjusted further from the parent until all non-child nodes are no less than the values of their adjacent children, and the maximum heap is constructed.

Suppose there are n nodes in the tree and the nodes are numbered from 0 to n-1. For the node numbered I, its parent is (i-1)/2. The left child node is numbered i2+1, and the right child node is numbered I2 +2. The last node is numbered n-1, and its parent node is numbered (n-2)/2. The tree is adjusted from the node numbered (n-2)/2.

As shown in the figure below, the last node is 7 and its parent node is 20. The maximum heap is constructed from 20. After construction is complete, it moves to the next parent node until all parent nodes are constructed.

The idea has been combed out, let’s see how RxSwift is implemented.

Pass in the initialization method of PriorityQueue a method to compare the priority of two elements and determine whether the elements are equal. _elements is used to hold elements in the queue.

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
    }
}
Copy the code

Get the element with the highest priority, that is, return the first element of _elements:

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

When an element is queued, the element is first added to the end of the array _elements, which is equivalent to adding another node to the end of the heap tree. In this case, the array needs to be adjusted according to the priority of this node and its parent. Because the tree structure before the element is added already meets the maximum heap requirement, you now only need to focus on the priority of the last node and its parent, and if the last node has a higher priority, adjust the last node and its parent. And so on all the way up to the top of the tree.

mutating func enqueue(_ element: Element) {
    _elements.append(element)
    bubbleToHigherPriority(_elements.count - 1)}// Adjust the element from initialUnbalancedIndex to the higher priority
private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
    // Make sure initialUnbalancedIndex is within the index range of _elements
    precondition(initialUnbalancedIndex >= 0)
    precondition(initialUnbalancedIndex < _elements.count)

    var unbalancedIndex = initialUnbalancedIndex

    while unbalancedIndex > 0 {
        // unbalancedIndex is an unsorted index
        // parentIndex is the index of the parent node of the unsorted node
        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
    }
}
Copy the code

We remove the highest priority element from the queue, which means we remove the first element in the array, and we may need to remove any element in the array. The problem then boils down to how to remove the element at the specified index.

When it comes to the element at the specified index of the removed, you will be at the specified index of the last element of an array of elements and swap places, and then removes the last element, so the last element in the array was moved to the specified index, and that could undermine the rules of the maximum heap, so want to specify the location of the elements according to their priority floating down, Swap the largest of its children with it, ensuring that the priority of the specified index is greater than that of all its children, and then float the element at the specified index up by priority, ensuring that the element at the specified index has a priority less than or equal to that of its parent. The code is as follows:

Mutating func dequeue() -> Element? { guardlet front = peek() else {
        return nil
    }

    removeAt(0)

    returnMutating func remove(_ element: element) {for i in 0 ..< _elements.count {
        if _isEqual(_elements[i], element) {
            removeAt(i)
            returnPrivate 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)}} // Bubble to low priority private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) { precondition(initialUnbalancedIndex >= 0) precondition(initialUnbalancedIndex < _elements.count) var unbalancedIndex = initialUnbalancedIndexwhile 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
        }

        ifrightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) { highestPriorityIndex = rightChildIndex } guard highestPriorityIndex ! = unbalancedIndexelse { break }

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

At this point, all the functionality of RxSwift’s PriorityQueue has been implemented, which uses maximum heap sort and inserts and deletes elements in order (log(n)) time.