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:
- How to create a binary tree using an array in Swift - part 1
- How to create a binary tree using an array in Swift - part 2
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.
- Top - Remove and return the top priority element from the queue
- Insert - Add a new element to the queue
- Remove - Remove an element from the queue
- Peek - Return the top priority element from the queue, without removing the element
- 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)
14 return topElem
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
79 func testInsert_emptyQueue_added() throws {
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.