Swift- Schematic priority queue implementation

“This is the second day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

👋

Wechat: RyukieW
📦 Archive of technical articles
🐙 making

My personal project	Minesweeper Elic Endless Ladder	Dream of books	Privacy Access Record
type	The game	financial	tool
AppStore	Elic	Umemi	Privacy Access Record

More columns:

The independent development of Lawliet

Lawliet’s iOS garden party

Lawliet’s underlying iOS lab

Lawliet’s iOS Reverse lab

Lawliet’s brush book

Lawliet’s Flutter Lab

What is a priority queue

If there is such a data stream 1,2,3,4,5,6,7,8, we need to find the element that meets the condition (maximum or minimum) according to a certain priority, and every time after taking out the element with the highest priority, the internal element can still ensure that the element with the highest priority is at the top according to the given priority.

Maximum heap & minimum heap

The heapDivided intoThe maximum heap 和 The minimum heapIn fact, it isComplete binary tree
- The maximum heap
  - Each node is required to have elements greater than or equal to its child
- The minimum heap
  - Node elements are required to be less than or equal to their left and right children
They make no demands on the relationship between the size of the child and the size of the child

Why use`Binary tree`To implement it?

The complexity is even higher if you use arrays

Insert elements

For the following data stream, we insert the data in order and return the largest element each time, we can use the priority queue (maximum heap).

Step 1

Insert 1 and 5 to see the binary tree structure
Leaf node 5 > 1 does not comply with the priority rule and needs to be switched
The equivalent array is
- [5, 1)

Step 2

Insert the 6
- Each insert is inserted to the current deepest position from left to right, or to create the next layer
If 6 is larger than parent node 5, adjust the position
Exchange of 5 6
The equivalent array is
- [6, 1, 5]

Step 3

Insert the 2
- This floor is full. The next one is on the left
2 is larger than the parent node 1 and needs to be adjusted
Exchange of 2 1
The equivalent array is
- [6, 2, 5, 1)

Step 4

Insert the 7
7 is larger than the parent node 2 and needs to be adjusted
Exchange of July 2
- The parent of 7 becomes 6, which needs to be adjusted
- Exchange of July 6
The equivalent array is
- [7, 6, 5, 1, 2]

Step 5

Insert 4, parent node is 5, no need to adjust
The equivalent array is
- [7, 6, 5, 1, 2, 4]

Step 6

Insert 3, the parent node is 5, no need to adjust
The equivalent array is
- [7, 6, 5, 1, 2, 4, 3]

Step 7

Insert the eight
- The next layer
Greater than parent 1, switch
Greater than parent 6, switch
Greater than parent 7, switch
The equivalent array is
- [8, 7, 5, 6, 2, 4, 3, 1]

3.1 Basic data structure

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(a) -> Element? {
        return _elements.first
    }
    
    public func array(a)- > [Element] {
        return _elements
    }

    public var isEmpty: Bool {
        return _elements.count = = 0
    }
    
    public var count: Int {
        return _elements.count
    }
}
Copy the code

3.2 Insert Logic

/ / insert
public mutating func enqueue(_ element: Element) {
    _elements.append(element)
    bubbleToHigherPriority(_elements.count - 1)}/ / climb
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
    }
}
Copy the code

Remove elements

We also continue to investigate the removal of elements using the priority queue data structure completed above as an example.

Here we plan to remove 5 elements (currently table A below)
Now swap it with the tail element
Remove the tail element
Check if the element at A needs to climb
- is
  - The buoyancy
    - Here, element A is 1, smaller than the parent node 8, and no action is required
Check if the element at A needs to sink
- is
  - The decline in
    - Here, element A is 1, less than the child node, and the sinking process is carried out

4.1 Removal and sinking logic implementation

private mutating func removeAt(_ index: Int) {
    // is the last element
    let removingLast = index = = _elements.count - 1
    if !removingLast {
        _elements.swapAt(index, _elements.count - 1)}_ = _elements.popLast()

    if !removingLast {
        // Check and hold the priority queue elements
        bubbleToHigherPriority(index)
        bubbleToLowerPriority(index)
    }
}

private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
    precondition(initialUnbalancedIndex > = 0)
    precondition(initialUnbalancedIndex < _elements.count)

    var unbalancedIndex = initialUnbalancedIndex
    while true {
        // According to the binary tree structure, the index of the left leaf of the current node is unbalancedIndex * 2 + 1
        let leftChildIndex = unbalancedIndex * 2 + 1
        // According to the binary tree structure, the index of the right leaf of the current node is unbalancedIndex * 2 + 2
        let rightChildIndex = unbalancedIndex * 2 + 2

        var highestPriorityIndex = unbalancedIndex

        // The left leaf is taller
        if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
            highestPriorityIndex = leftChildIndex
        }

        The right leaf is taller
        if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
            highestPriorityIndex = rightChildIndex
        }

        guard highestPriorityIndex ! = unbalancedIndex else { 
            break // Do not adjust the priority
        }

        // Swap elements
        _elements.swapAt(highestPriorityIndex, unbalancedIndex)

        // Save the subscript of higher priority and continue the comparison
        unbalancedIndex = highestPriorityIndex
    }
}
Copy the code

Complete realization of Swift

The following priority queue implementation is a reference to 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(a) -> Element? {
        return _elements.first
    }
    
    public func array(a)- > [Element] {
        return _elements
    }

    public var isEmpty: Bool {
        return _elements.count = = 0
    }
    
    public var count: Int {
        return _elements.count
    }

    public mutating func dequeue(a) -> 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
    }
}
Copy the code

Swift- Schematic priority queue implementation

👋

What is a priority queue

Maximum heap & minimum heap

Why useBinary treeTo implement it?

Insert elements

3.1 Basic data structure

3.2 Insert Logic

Remove elements

4.1 Removal and sinking logic implementation

Complete realization of Swift

Related Posts

The iOS keyboard no longer blocks input controls

ReactiveObjC Quick Start for ReactiveCocoa

Summary of Flutter thematic directories

Why use`Binary tree`To implement it?