# How to create a binary tree using an array in Swift - part 2

This is the second part on my notes on creating a binary tree using an array in Swift. This is based on reading of Advanced Algorithms and Data Structures by Marcello La Rocca. In this article, I'll implement the code for the priority queue.

An overview of a Priority Queue was presented in part 1.

These are my notes on the book
Advanced Algorithms and Data Structures - by Marcello La Rocca
May 2021, ISBN 9781617295485

Related articles on Advanced Algorithms and Data Structures:

## Priority List in Swift

Start with defining a structure for the Elements that will be placed in the priority queue. The initial code for the PriorityQueue simply contains an array of elements. Unit tests are included in the project so these can be used to validate the various functions on the priority queue, as they are written. There is not much to the PriorityQueue yet and not much testing to be done on Element.

There is a design decision as to whether the priority of an element is a property of the element or whether elements do not have priority. In the second case the priority queue could be constructed of tuples containing an element and a priority. I will go with the element containing a property for its priority for now.

#### Element

1struct Element : Identifiable {
2    var id = UUID()
3    var value: String
4    var priority: Int
5    var color: Color
6
7    init(_ value: String, priority: Int, color: Color = .white) {
8        self.value = value
9        self.priority = priority
10        self.color = color
11    }
12}

#### PriorityQueue

1struct PriorityQueue {
2    var elements: [Element]
3}

#### ElementTests

1import XCTest
2import SwiftUI
3
4@testable import BinaryTreeApp
5
6final class ElementTests: XCTestCase {
7    func testCreateElement_priority10_success() throws {
8        // 1. Arrange
9        let elem = Element("test", priority: 10)
10
11        // 2. Act
12
13        // 3. Assert
14        XCTAssertEqual(elem.value, "test")
15        XCTAssertEqual(elem.priority, 10)
16        XCTAssertEqual(elem.color, Color.white)
17    }
18
19    func testSetElementColor_blue_success() throws {
20        // 1. Arrange
21        var elem = Element("test", priority: 1)
22
23        // 2. Act
24        elem.color = .blue
25
26        // 3. Assert
27        XCTAssertEqual(elem.color, Color.blue)
28    }
29
30    func testSetElementPriority_200_success() throws {
31        // 1. Arrange
32        var elem = Element("test", priority: 1)
33
34        // 2. Act
35        elem.priority = 200
36
37        // 3. Assert
38        XCTAssertEqual(elem.priority, 200)
39    }
40
41    func testSetElementValue_testValue_success() throws {
42        // 1. Arrange
43        var elem = Element("test", priority: 1)
44
45        // 2. Act
46        elem.value = "test value"
47
48        // 3. Assert
49        XCTAssertEqual(elem.value, "test value")
50    }
51}

## Bubble Up method in Priority Queue

The next step is to implement the internal functions of the priority queue that will be used by the external API. The first of these is the bubbleUp method based on the pseudocode in the book. The bubbleUp method takes a specified element index in the priority queue and compares its priority to that of its parent and if necessary swaps the elements. This process is repeated for each element in the while loop until the element is in the correct priority position in the queue.

There are two implementations of the bubbleUp method as detailed in the book. The first of these compares each element in turn with its parent and swaps the elements if necessary. The second method places the selected element in a temporary variable, and for each step in the while loop, it only needs to set the child element to its parent until the final element is reached and then assigns the temporary variable to that position in the queue. The second implementation is estimated to be more performant as it will have less assignments to make, however the first method in swift uses tuple assignment to make the swaps, which is more efficient than using a temporary variable.

Unit tests were written for the bubble up method and these pass when either bubbleUp method is used. I will defer measuring performance for now.

#### Initial bubbleUp code

1    mutating func bubbleUp(index: Int) {
2        var parentIndex = index
3        while parentIndex > 0 {
4            let currentIndex = parentIndex
5            parentIndex = (currentIndex - 1) / 2
6            if elements[parentIndex].priority > elements[currentIndex].priority
7            {
8                (elements[parentIndex],  elements[currentIndex]) = (elements[currentIndex],  elements[parentIndex])
9            }
10            else {
11                break
12            }
13        }
14    }

#### Optimised bubbleUp code

1    mutating func bubbleUp(index: Int) {
2        var currentIndex = index
3        let current = elements[index]
4        while currentIndex > 0 {
5            let parentIndex = (currentIndex - 1) / 2
6            if elements[parentIndex].priority > current.priority
7            {
8                elements[currentIndex] = elements[parentIndex]
9                currentIndex = parentIndex
10            } else {
11                break
12            }
13        }
14        elements[currentIndex] = current
15    }

#### bubbleUp - Unit Tests

1    // MARK: Bubble Up tests
2
3    func testBubbleUp_two_swapped() throws {
4        // 1. Arrange
5        var priorityQueue = PriorityQueue(elements: [
6            Element("10", priority: 10),
7            Element("8", priority: 8)
8        ])
9
10        // 2. Act
11        priorityQueue.bubbleUp(index: 1)
12
13        // 3. Assert
14        XCTAssertEqual(priorityQueue.elements[0].priority, 8)
15        XCTAssertEqual(priorityQueue.elements[1].priority, 10)
16    }
17
18    func testBubbleUp_two_noSwap() throws {
19        // 1. Arrange
20        var priorityQueue = PriorityQueue(elements: [
21            Element("1", priority: 1),
22            Element("2", priority: 2)
23        ])
24
25        // 2. Act
26        priorityQueue.bubbleUp(index: 1)
27
28        // 3. Assert
29        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
30        XCTAssertEqual(priorityQueue.elements[1].priority, 2)
31    }
32
33    func testBubbleUp_ten_lastToFirst() throws {
34        // 1. Arrange
35        var priorityQueue = PriorityQueue(elements: [
36            Element("abc", priority: 5),
37            Element("abc", priority: 6),
38            Element("abc", priority: 7),
39            Element("abc", priority: 8),
40            Element("abc", priority: 9),
41            Element("abc", priority: 10),
42            Element("abc", priority: 11),
43            Element("abc", priority: 12),
44            Element("abc", priority: 13),
45            Element("abc", priority: 2)
46        ])
47
48        print("Before")
49        _ = priorityQueue.elements.map {print("elem priority = \($0.priority)")} 50 // 2. Act 51 priorityQueue.bubbleUp(index: priorityQueue.elements.count-1) 52 53 print("After") 54 _ = priorityQueue.elements.map {print("elem priority = \($0.priority)")}
55        // 3. Assert
56        XCTAssertEqual(priorityQueue.elements[0].priority, 2)
57        XCTAssertEqual(priorityQueue.elements.count, 10)
58    }
59
60    func testBubbleUp2_ten_lastToFirst() throws {
61        // 1. Arrange
62        var priorityQueue = PriorityQueue(elements: [
63            Element("abc", priority: 5),
64            Element("abc", priority: 6),
65            Element("abc", priority: 7),
66            Element("abc", priority: 8),
67            Element("abc", priority: 9),
68            Element("abc", priority: 10),
69            Element("abc", priority: 11),
70            Element("abc", priority: 12),
71            Element("abc", priority: 13),
72            Element("abc", priority: 2)
73        ])
74
75        // 2. Act
76        priorityQueue.bubbleUp2(index: priorityQueue.elements.count-1)
77
78        // 3. Assert
79        XCTAssertEqual(priorityQueue.elements[0].priority, 2)
80        XCTAssertEqual(priorityQueue.elements.count, 10)
81    }
82
83    func testBubbleUp_ten_middleOneMove() throws {
84        // 1. Arrange
85        var priorityQueue = PriorityQueue(elements: [
86            Element("abc", priority: 1),
87            Element("abc", priority: 5),
88            Element("abc", priority: 3),
89            Element("abc", priority: 4),
90            Element("abc", priority: 2),
91            Element("abc", priority: 6),
92            Element("abc", priority: 7),
93            Element("abc", priority: 8),
94            Element("abc", priority: 9),
95            Element("abc", priority: 10)
96        ])
97
98        // 2. Act
99        priorityQueue.bubbleUp(index: 4)
100
101        // 3. Assert
102        XCTAssertEqual(priorityQueue.elements[4].priority, 5)
103        XCTAssertEqual(priorityQueue.elements[1].priority, 2)
104        XCTAssertEqual(priorityQueue.elements[9].priority, 10)
105        XCTAssertEqual(priorityQueue.elements.count, 10)
106    }

## Push Down method in Priority Queue

The next internal method required in the priority queue is the pushDown method. This is the reverse of the bubbleUp method, whereby an element is examined and compared to its children and if it is a lower priority then those elements are swapped. This process is repeated until the specified element is in the correct position in the priority queue. Similar to the bubbleUp method, there is an optimisation that can be made to use a temporary variable for the specified element and move the elements from parent to child until the appropriate level is reached, and then add in the selected element. There is a formula used to identify the first leaf index of the binary tree, which is used to determine the path to push down towards.

#### First Leaf Index:

\begin{aligned} firstLeafIndex = (elements.count - 2) / 2 + 1 \end{aligned}

There is another difference between the bubbleUp method and the pushDwon method in that the highest priority child element needs to be identified to make the swap. In the bubbleUp there is only one parent to swap with, but there is a choice to identify the correct child when pushing down. The helper method highestPriorityChild is created to identify the correct child element. I did discover an issue with the initial implementation of highestPriorityChild where an index out of bounds error would occur if there was no right child index, so a check was added for that. This is where unit tests can be great.

#### highestPriorityChild

1    fileprivate func highestPriorityChild(index: Int) -> Int {
2        let leftChildIndex = (2 * index) + 1
3        let rightChildIndex = 2 * (index + 1)
4        if rightChildIndex > (elements.count - 1) || elements[leftChildIndex].priority < elements[rightChildIndex].priority {
5            return leftChildIndex
6        } else {
7            return rightChildIndex
8        }
9    }

#### Initial pushDown code

1    mutating func pushDown(index: Int) {
2        var currentIndex = index
3        let firstLeafIndex = (elements.count - 2) / 2 + 1
4        while currentIndex < firstLeafIndex {
5            let (child, childIndex) = highestPriorityChild(index: currentIndex)
6            if child.priority < elements[currentIndex].priority {
7                (elements[currentIndex],  elements[childIndex]) = (elements[childIndex],  elements[currentIndex])
8                currentIndex = childIndex
9            } else {
10                break
11            }
12        }
13    }

#### Optimised pushDown code

1    mutating func pushDown(index: Int) {
2        var currentIndex = index
3        let current = elements[index]
4        let firstLeafIndex = (elements.count - 2) / 2 + 1
5        while currentIndex < firstLeafIndex {
6            let (child, childIndex) = highestPriorityChild(index: currentIndex)
7            if child.priority < current.priority {
8                elements[currentIndex] = elements[childIndex]
9                currentIndex = childIndex
10            } else {
11                break
12            }
13        }
14        elements[currentIndex] = current
15    }

#### pushDown - Unit Tests

1    // MARK: Push Down tests
2
3    func testPushDown_ten_firstDown() throws {
4        // 1. Arrange
5        var priorityQueue = PriorityQueue(elements: [
6            Element("abc", priority: 15),
7            Element("abc", priority: 2),
8            Element("abc", priority: 3),
9            Element("abc", priority: 4),
10            Element("abc", priority: 5),
11            Element("abc", priority: 6),
12            Element("abc", priority: 7),
13            Element("abc", priority: 8),
14            Element("abc", priority: 9),
15            Element("abc", priority: 10)
16        ])
17
18        // 2. Act
19        priorityQueue.pushDown(index: 0)
20
21        // 3. Assert
22        XCTAssertEqual(priorityQueue.elements[0].priority, 2)
23        XCTAssertEqual(priorityQueue.elements[1].priority, 4)
24        XCTAssertEqual(priorityQueue.elements[3].priority, 8)
25        XCTAssertEqual(priorityQueue.elements[7].priority, 15)
26        XCTAssertEqual(priorityQueue.elements.count, 10)
27    }
28
29    func testPushDown_one_noMove() throws {
30        // 1. Arrange
31        var priorityQueue = PriorityQueue(elements: [
32            Element("abc", priority: 15)
33        ])
34
35        // 2. Act
36        priorityQueue.pushDown(index: 0)
37
38        // 3. Assert
39        XCTAssertEqual(priorityQueue.elements[0].priority, 15)
40        XCTAssertEqual(priorityQueue.elements.count, 1)
41    }
42
43    func testPushDown_two_noMove() throws {
44        // 1. Arrange
45        var priorityQueue = PriorityQueue(elements: [
46            Element("abc", priority: 1),
47            Element("abc", priority: 2)
48        ])
49
50        // 2. Act
51        priorityQueue.pushDown(index: 0)
52
53        // 3. Assert
54        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
55        XCTAssertEqual(priorityQueue.elements.count, 2)
56    }
57
58    func testPushDown_two_moveLeft() throws {
59        // 1. Arrange
60        var priorityQueue = PriorityQueue(elements: [
61            Element("abc", priority: 2),
62            Element("abc", priority: 1)
63        ])
64
65        // 2. Act
66        priorityQueue.pushDown(index: 0)
67
68        // 3. Assert
69        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
70        XCTAssertEqual(priorityQueue.elements.count, 2)
71    }
72
73    func testPushDown_three_moveLeft() throws {
74        // 1. Arrange
75        var priorityQueue = PriorityQueue(elements: [
76            Element("abc", priority: 5),
77            Element("abc", priority: 1),
78            Element("abc", priority: 2)
79        ])
80
81        // 2. Act
82        priorityQueue.pushDown(index: 0)
83
84        // 3. Assert
85        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
86        XCTAssertEqual(priorityQueue.elements.count, 3)
87    }
88
89    func testPushDown_four_moveRight() throws {
90        // 1. Arrange
91        var priorityQueue = PriorityQueue(elements: [
92            Element("abc", priority: 5),
93            Element("abc", priority: 2),
94            Element("abc", priority: 1),
95            Element("abc", priority: 3)
96        ])
97
98        // 2. Act
99        priorityQueue.pushDown(index: 0)
100
101        // 3. Assert
102        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
103        XCTAssertEqual(priorityQueue.elements.count, 4)
104    }
105
106    func testPushDown_ten_middleDown() throws {
107        // 1. Arrange
108        var priorityQueue = PriorityQueue(elements: [
109            Element("abc", priority: 1),
110            Element("abc", priority: 2),
111            Element("abc", priority: 3),
112            Element("abc", priority: 14),
113            Element("abc", priority: 5),
114            Element("abc", priority: 6),
115            Element("abc", priority: 7),
116            Element("abc", priority: 8),
117            Element("abc", priority: 9),
118            Element("abc", priority: 10)
119        ])
120
121        // 2. Act
122        priorityQueue.pushDown(index: 3)
123
124        // 3. Assert
125        XCTAssertEqual(priorityQueue.elements[3].priority, 8)
126        XCTAssertEqual(priorityQueue.elements[7].priority, 14)
127        XCTAssertEqual(priorityQueue.elements.count, 10)
128    }
129
130    func testPushDown_tenLast_noMove() throws {
131        // 1. Arrange
132        var priorityQueue = PriorityQueue(elements: [
133            Element("abc", priority: 1),
134            Element("abc", priority: 2),
135            Element("abc", priority: 3),
136            Element("abc", priority: 4),
137            Element("abc", priority: 5),
138            Element("abc", priority: 6),
139            Element("abc", priority: 7),
140            Element("abc", priority: 8),
141            Element("abc", priority: 9),
142            Element("abc", priority: 10)
143        ])
144
145        // 2. Act
146        priorityQueue.pushDown(index: 9)
147
148        // 3. Assert
149        XCTAssertEqual(priorityQueue.elements[9].priority, 10)
150        XCTAssertEqual(priorityQueue.elements.count, 10)
151    }

## Code for peek and Top operations

Now we can implement the public API for the priority queue.

1. Top - Remove and return the top priority element from the queue
2. Insert - Add a new element to the queue
3. Remove - Remove an element from the queue
4. Peek - Return the top priority element from the queue, without removing the element
5. Update - Update the priority of an element in the queue

The easiest to implement is the peek method as it simply returns a copy of the highest priority element in the queue without altering the queue.

The top method is similar in that it returns the highest priority element, but it removes this from the queue. The challenge is to restore the binary tree when the first element is removed. The pseudocode in the book solves this in an elegant way by moving the last element to the first and then use the pushDown operation on the first element in the array.

I've implemented both peek and top to return an optional element, which means the calling code will have to check the value is not nil. There is some logic to check in case the array is empty or only has one element, but the complicated logic has already been done in the pushDown method.

#### peek operation

1    func peek() -> Element? {
2        return elements.first
3    }

#### top operation

1    mutating func top() -> Element? {
2        guard !elements.isEmpty else {
3            print("The list is empty")
4            return nil
5        }
6
7        let lastElem = elements.removeLast()
8        if elements.isEmpty {
9            return lastElem
10        } else {
11            if let topElem = elements.first {
12                elements[0] = lastElem
13                pushDown(index: 0)
15            }
16        }
17        return nil
18    }

#### top - Unit Tests

1    // MARK: Top tests
2
3    func testTop_two_leavesOne() throws {
4        // 1. Arrange
5        var priorityQueue = PriorityQueue(elements: [
6            Element("abc", priority: 2),
7            Element("abc", priority: 3)
8        ])
9
10        // 2. Act
11        _ = priorityQueue.top()
12
13        // 3. Assert
14        XCTAssertEqual(priorityQueue.elements[0].priority, 3)
15        XCTAssertEqual(priorityQueue.elements.count, 1)
16    }
17
18    func testTop_empty_nil() throws {
19        // 1. Arrange
20        var priorityQueue = PriorityQueue(elements: [])
21
22        // 2. Act
23        let result = priorityQueue.top()
24
25        // 3. Assert
26        XCTAssertNil(result)
27    }
28
29    func testTop_repeatThree_leavesTwo() throws {
30        // 1. Arrange
31        var priorityQueue = PriorityQueue(elements: [
32            Element("abc", priority: 1),
33            Element("abc", priority: 2),
34            Element("abc", priority: 3),
35            Element("abc", priority: 4),
36            Element("abc", priority: 5)
37        ])
38
39        // 2. Act
40        let one = priorityQueue.top()
41        let two = priorityQueue.top()
42        let three = priorityQueue.top()
43
44        // 3. Assert
45        XCTAssertEqual(one!.priority, 1)
46        XCTAssertEqual(two!.priority, 2)
47        XCTAssertEqual(three!.priority, 3)
48        XCTAssertEqual(priorityQueue.elements[0].priority, 4)
49        XCTAssertEqual(priorityQueue.elements[1].priority, 5)
50        XCTAssertEqual(priorityQueue.elements.count, 2)
51    }
52
53    func testTop_twoElements_thirdReturnsNil() throws {
54        // 1. Arrange
55        var priorityQueue = PriorityQueue(elements: [
56            Element("abc", priority: 1),
57            Element("abc", priority: 2)
58        ])
59
60        // 2. Act
61        _ = priorityQueue.top()
62        _ = priorityQueue.top()
63        let thirdElem = priorityQueue.top()
64
65        // 3. Assert
66        XCTAssertNil(thirdElem)
67        XCTAssertEqual(priorityQueue.elements.count, 0)
68    }
69
70    func testTop_oneElement_emptiesQueue() throws {
71        // 1. Arrange
72        var priorityQueue = PriorityQueue(elements: [
73            Element("abc", priority: 1)
74        ])
75
76        // 2. Act
77        let topElem = priorityQueue.top()
78
79        // 3. Assert
80        XCTAssertEqual(topElem?.priority, 1)
81        XCTAssertEqual(priorityQueue.elements.count, 0)
82        XCTAssertNil(priorityQueue.top())
83    }

## Code for insert operation

The insert operation is also straight forward with the use of the bubbleUp function already written. The new element is simply added to the end of the array and then bubbleUp is called on the last element in the array.

#### insert operation

1    mutating func insert(element: Element) {
2        elements.append(element)
3        bubbleUp(index: elements.count - 1)
4    }

#### insert - Unit Tests

1    // MARK: insert tests
2
3    func testInsert_top_movedToTop() throws {
4        // 1. Arrange
5        let newElem = Element("abc", priority: 1)
6        var priorityQueue = PriorityQueue(elements: [
7            Element("abc", priority: 2),
8            Element("abc", priority: 3),
9            Element("abc", priority: 4),
10            Element("abc", priority: 5),
11            Element("abc", priority: 6),
12            Element("abc", priority: 7),
13            Element("abc", priority: 8),
14            Element("abc", priority: 9),
15            Element("abc", priority: 10),
16            Element("abc", priority: 11)
17        ])
18
19        // 2. Act
20        priorityQueue.insert(element: newElem)
21
22        // 3. Assert
23        XCTAssertEqual(newElem, priorityQueue.peek())
24        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
25        XCTAssertEqual(priorityQueue.elements.count, 11)
26    }
27
28    func testInsert_middle_movedToMiddle() throws {
29        // 1. Arrange
30        let newElem = Element("abc", priority: 5)
31        var priorityQueue = PriorityQueue(elements: [
32            Element("abc", priority: 1),
33            Element("abc", priority: 2),
34            Element("abc", priority: 3),
35            Element("abc", priority: 4),
36            Element("abc", priority: 6),
37            Element("abc", priority: 7),
38            Element("abc", priority: 8),
39            Element("abc", priority: 9),
40            Element("abc", priority: 10),
41            Element("abc", priority: 11)
42        ])
43
44        // 2. Act
45        priorityQueue.insert(element: newElem)
46
47        // 3. Assert
48        XCTAssertEqual(newElem, priorityQueue.elements[4])
49        XCTAssertEqual(priorityQueue.elements[4].priority, 5)
50        XCTAssertEqual(priorityQueue.elements[10].priority, 6)
51        XCTAssertEqual(priorityQueue.elements.count, 11)
52    }
53
54    func testInsert_last_movedToEnd() throws {
55        // 1. Arrange
56        let newElem = Element("abc", priority: 15)
57        var priorityQueue = PriorityQueue(elements: [
58            Element("abc", priority: 1),
59            Element("abc", priority: 2),
60            Element("abc", priority: 3),
61            Element("abc", priority: 4),
62            Element("abc", priority: 5),
63            Element("abc", priority: 6),
64            Element("abc", priority: 7),
65            Element("abc", priority: 8),
66            Element("abc", priority: 9),
67            Element("abc", priority: 10)
68        ])
69
70        // 2. Act
71        priorityQueue.insert(element: newElem)
72
73        // 3. Assert
74        XCTAssertEqual(newElem, priorityQueue.elements[10])
75        XCTAssertEqual(priorityQueue.elements[10].priority, 15)
76        XCTAssertEqual(priorityQueue.elements.count, 11)
77    }
78
80        // 1. Arrange
81        let newElem = Element("abc", priority: 15)
82        var priorityQueue = PriorityQueue(elements: [])
83
84        // 2. Act
85        priorityQueue.insert(element: newElem)
86
87        // 3. Assert
88        XCTAssertEqual(newElem, priorityQueue.elements[0])
89        XCTAssertEqual(priorityQueue.elements.count, 1)
90    }

## Code for remove operation

The remove operation is not always included as part of the API for a priority queue. It can be beneficial when an item in a queue may no longer be required and needs to be removed. The most expensive step of removing an element is finding the element in the queue. In this code we rely on the Swift firstIndex(where:) function to get the index of the element in the collection. Similar to the top method, the last element in the array is removed and put in the place of the removed element.

Initially, I had logic in place to determine if the replaced element should call either bubbleUp or pushDown. However, since it is the last element that is inserted, we can just call pushDown to get the priority back to the correct state.

#### remove operation

1    mutating func remove(oldElement: Element) {
2        guard !elements.isEmpty else {
3            print("The list is empty")
4            return
5        }
6
7        if let index = elements.firstIndex( where: {$0 == oldElement} ) { 8 let lastElem = elements.removeLast() 9 if elements.isEmpty || lastElem == oldElement { 10 return 11 } else { 12 elements[index] = lastElem 13 pushDown(index: index) 14 } 15 } 16 } #### remove - Unit Tests 1 // MARK: Remove tests 2 3 func testRemove_first_pushDown() throws { 4 // 1. Arrange 5 var priorityQueue = PriorityQueue(elements: [ 6 Element("abc", priority: 1), 7 Element("abc", priority: 2), 8 Element("abc", priority: 3), 9 Element("abc", priority: 4), 10 Element("abc", priority: 5), 11 Element("abc", priority: 6), 12 Element("abc", priority: 7), 13 Element("abc", priority: 8), 14 Element("abc", priority: 9), 15 Element("abc", priority: 10) 16 ]) 17 18 // 2. Act 19 let elem = priorityQueue.elements[0] 20 priorityQueue.remove(oldElement: elem) 21 22 // 3. Assert 23 XCTAssertEqual(priorityQueue.elements[0].priority, 2) 24 XCTAssertEqual(priorityQueue.elements[1].priority, 4) 25 XCTAssertEqual(priorityQueue.elements[3].priority, 8) 26 XCTAssertEqual(priorityQueue.elements[7].priority, 10) 27 XCTAssertEqual(priorityQueue.elements.count, 9) 28 } 29 30 func testRemove_last_noMove() throws { 31 // 1. Arrange 32 var priorityQueue = PriorityQueue(elements: [ 33 Element("abc", priority: 1), 34 Element("abc", priority: 2), 35 Element("abc", priority: 3), 36 Element("abc", priority: 4), 37 Element("abc", priority: 5), 38 Element("abc", priority: 6), 39 Element("abc", priority: 7), 40 Element("abc", priority: 8), 41 Element("abc", priority: 9), 42 Element("abc", priority: 10) 43 ]) 44 45 // 2. Act 46 let elem = priorityQueue.elements[9] 47 priorityQueue.remove(oldElement: elem) 48 49 // 3. Assert 50 XCTAssertEqual(priorityQueue.elements[0].priority, 1) 51 XCTAssertEqual(priorityQueue.elements[8].priority, 9) 52 XCTAssertEqual(priorityQueue.elements.count, 9) 53 } 54 55 func testRemove_secondLast_pushDown() throws { 56 // 1. Arrange 57 var priorityQueue = PriorityQueue(elements: [ 58 Element("abc", priority: 1), 59 Element("abc", priority: 2), 60 Element("abc", priority: 3), 61 Element("abc", priority: 4), 62 Element("abc", priority: 5), 63 Element("abc", priority: 6), 64 Element("abc", priority: 7), 65 Element("abc", priority: 8), 66 Element("abc", priority: 9), 67 Element("abc", priority: 10) 68 ]) 69 70 // 2. Act 71 let elem = priorityQueue.elements[8] 72 priorityQueue.remove(oldElement: elem) 73 74 // 3. Assert 75 XCTAssertEqual(priorityQueue.elements[0].priority, 1) 76 XCTAssertEqual(priorityQueue.elements[8].priority, 10) 77 XCTAssertEqual(priorityQueue.elements.count, 9) 78 } 79 80 func testRemove_two_pushDown() throws { 81 // 1. Arrange 82 var priorityQueue = PriorityQueue(elements: [ 83 Element("abc", priority: 1), 84 Element("abc", priority: 2), 85 Element("abc", priority: 3), 86 Element("abc", priority: 4), 87 Element("abc", priority: 5), 88 Element("abc", priority: 6), 89 Element("abc", priority: 7), 90 Element("abc", priority: 8), 91 Element("abc", priority: 9), 92 Element("abc", priority: 10) 93 ]) 94 95 // 2. Act 96 let elem1 = priorityQueue.elements[3] 97 priorityQueue.remove(oldElement: elem1) 98 let elem2 = priorityQueue.elements[1] 99 priorityQueue.remove(oldElement: elem2) 100 101 // 3. Assert 102 XCTAssertEqual(priorityQueue.elements[1].priority, 5) 103 XCTAssertEqual(priorityQueue.elements.count, 8) 104 } 105 106 func testRemove_oneEmpty_noChange() throws { 107 // 1. Arrange 108 var priorityQueue = PriorityQueue(elements: []) 109 110 // 2. Act 111 let elem = Element("abc", priority: 23) 112 priorityQueue.remove(oldElement: elem) 113 114 // 3. Assert 115 XCTAssertTrue(priorityQueue.elements.isEmpty) 116 XCTAssertEqual(priorityQueue.elements.count, 0) 117 } ## Code for update operations Similar to remove operation, the most expensive step of updating an element is finding the element in the queue. There is no other cost to the update if some of the contents of the element need to be changed. However, if the priority needs to be changed, then the queue needs to be reset to priority order. Again, similar to remove operation, either bubbleUp or pushDown is called depending on the new priority being higher or lower than the old priority. #### update operation 1 mutating func update(oldElement:Element, newPriority: Int) { 2 if let index = elements.firstIndex( where: {$0 == oldElement} ) {
3            let oldPriority = oldElement.priority
4            var newElement = oldElement
5            newElement.priority = newPriority
6            elements[index] = newElement
7            if newPriority < oldPriority {
8                bubbleUp(index: index)
9            } else if newPriority > oldPriority {
10                pushDown(index: index)
11            }
12        }
13    }

#### update - Unit Tests

1    // MARK: update tests
2
3    func testUpdate_first_pushDown() throws {
4        // 1. Arrange
5        var priorityQueue = PriorityQueue(elements: [
6            Element("abc", priority: 1),
7            Element("abc", priority: 2),
8            Element("abc", priority: 3),
9            Element("abc", priority: 4),
10            Element("abc", priority: 5),
11            Element("abc", priority: 6),
12            Element("abc", priority: 7),
13            Element("abc", priority: 8),
14            Element("abc", priority: 9),
15            Element("abc", priority: 10)
16        ])
17
18        // 2. Act
19        let elem = priorityQueue.elements[0]
20        priorityQueue.update(oldElement: elem, newPriority: 25)
21
22        // 3. Assert
23        XCTAssertEqual(priorityQueue.elements[0].priority, 2)
24        XCTAssertEqual(priorityQueue.elements[7].priority, 25)
25        XCTAssertEqual(priorityQueue.elements.count, 10)
26    }
27
28    func testUpdate_first_noMove() throws {
29        // 1. Arrange
30        var priorityQueue = PriorityQueue(elements: [
31            Element("abc", priority: 10),
32            Element("abc", priority: 20),
33            Element("abc", priority: 30),
34            Element("abc", priority: 40),
35            Element("abc", priority: 50),
36            Element("abc", priority: 60),
37            Element("abc", priority: 70),
38            Element("abc", priority: 80),
39            Element("abc", priority: 90),
40            Element("abc", priority: 100)
41        ])
42
43        // 2. Act
44        let elem = priorityQueue.elements[0]
45        priorityQueue.update(oldElement: elem, newPriority: 1)
46
47        // 3. Assert
48        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
49        XCTAssertEqual(priorityQueue.elements[1].priority, 20)
50        XCTAssertEqual(priorityQueue.elements.count, 10)
51    }
52
53    func testUpdate_middle_pushDown() throws {
54        // 1. Arrange
55        var priorityQueue = PriorityQueue(elements: [
56            Element("abc", priority: 1),
57            Element("abc", priority: 2),
58            Element("abc", priority: 3),
59            Element("abc", priority: 4),
60            Element("abc", priority: 5),
61            Element("abc", priority: 6),
62            Element("abc", priority: 7),
63            Element("abc", priority: 8),
64            Element("abc", priority: 9),
65            Element("abc", priority: 10)
66        ])
67
68        // 2. Act
69        let elem = priorityQueue.elements[4]
70        priorityQueue.update(oldElement: elem, newPriority: 25)
71
72        // 3. Assert
73        XCTAssertEqual(priorityQueue.elements[4].priority, 10)
74        XCTAssertEqual(priorityQueue.elements[9].priority, 25)
75        XCTAssertEqual(priorityQueue.elements.count, 10)
76    }
77
78    func testUpdate_middle_bubbleUp() throws {
79        // 1. Arrange
80        var priorityQueue = PriorityQueue(elements: [
81            Element("abc", priority: 2),
82            Element("abc", priority: 3),
83            Element("abc", priority: 4),
84            Element("abc", priority: 5),
85            Element("abc", priority: 6),
86            Element("abc", priority: 7),
87            Element("abc", priority: 8),
88            Element("abc", priority: 9),
89            Element("abc", priority: 10),
90            Element("abc", priority: 11)
91        ])
92
93        // 2. Act
94        let elem = priorityQueue.elements[4]
95        priorityQueue.update(oldElement: elem, newPriority: 1)
96
97        // 3. Assert
98        XCTAssertEqual(priorityQueue.elements[0].priority, 1)
99        XCTAssertEqual(priorityQueue.elements.count, 10)
100    }
101
102    func testUpdate_last_bubbleUp() throws {
103        // 1. Arrange
104        var priorityQueue = PriorityQueue(elements: [
105            Element("abc", priority: 20),
106            Element("abc", priority: 30),
107            Element("abc", priority: 40),
108            Element("abc", priority: 50),
109            Element("abc", priority: 60),
110            Element("abc", priority: 70),
111            Element("abc", priority: 80),
112            Element("abc", priority: 90),
113            Element("abc", priority: 100),
114            Element("abc", priority: 110)
115        ])
116
117        // 2. Act
118        let elem = priorityQueue.elements[9]
119        priorityQueue.update(oldElement: elem, newPriority: 35)
120
121        // 3. Assert
122        XCTAssertEqual(priorityQueue.elements[0].priority, 20)
123        XCTAssertEqual(priorityQueue.elements.count, 10)
124    }
125
126    func testUpdate_last_noMove() throws {
127        // 1. Arrange
128        var priorityQueue = PriorityQueue(elements: [
129            Element("abc", priority: 20),
130            Element("abc", priority: 30),
131            Element("abc", priority: 40),
132            Element("abc", priority: 50),
133            Element("abc", priority: 60),
134            Element("abc", priority: 70),
135            Element("abc", priority: 80),
136            Element("abc", priority: 90),
137            Element("abc", priority: 100),
138            Element("abc", priority: 110)
139        ])
140
141        // 2. Act
142        let elem = priorityQueue.elements[9]
143        priorityQueue.update(oldElement: elem, newPriority: 200)
144
145        // 3. Assert
146        XCTAssertEqual(priorityQueue.elements[9].priority, 200)
147        XCTAssertEqual(priorityQueue.elements.count, 10)
148    }

## Conclusion

This is the second part of implementing a priority queue using an array in Swift. Part 1 walked through the concepts of the public API, while this article developed the swift code to implement the Priority Queue. The public API relies on the two internal functions (bubbleUp and pushDown) to get the queue back into priority order after an operation. Once these functions are in place the implementation of the public operations is more straight forward.

Next, I would like to look into populating the priority queue and measuring performance. There is also the question of access, the internal functions bubbleUp and pushDown have been written with public access so that unit tests can be written to validate their functionality. These should ideally be fileprivate and the unit testing to be done on the public API.