Author: APPCODA EDITORIAL TEAM, 2019-01-07
Translator: Roc Zhang; Proofreading: PMST, NUMbbbbb; Finalized: Forelax
In computer science, there are many problems that can improve the time complexity of algorithms by implementing the underlying data structures as priority queues. One example is Dijkstra’s shortest path algorithm, which uses priority queues to search a graph for the shortest path between two vertices.
Unfortunately, the default implementation of priority queues is not provided in Swift’s standard library. So we’ll look at how to implement heap-based priority queues ourselves.
If you want to do this together in your own IDE, click here to get the source code.
What is a priority queue?
A priority queue is a data structure that can efficiently sort objects with relative priority. It sorts objects in the queue one by one according to the priority of each object in the queue.
Let’s say you’ve created a series of tasks and are going to run them at some point in the future. Using priority queues can make these tasks perform as you expect.
In the next article, we will use the heap structure to implement our priority queue.
What is a heap?
We can think of a heap as a tree with at most two children per node, but unlike trees, adding new nodes to the heap is done as far to the top left as possible. As shown below:
At the same time, the heap also has some characteristics related to the relative size relationship between nodes. A minimal heap (the one we’re going to use) has the property that each node is smaller than its children. The largest pile is just the opposite.
To be able to maintain this property, we need to do something to get the correct order of nodes. When we insert a new node, we place it in the first free position starting at the top left of the tree. If the minimum heap property is not established after placement, the node is swapped with its parent until the minimum heap property is established. The following figure shows inserting the number 2 into an existing minimum heap.
When moving an object out of the queue, restrict the operation to one end of the queue. We will do this by limiting the deletion of only the root node. When the root node is removed, it is replaced by the top rightmost node. Since there is a high probability that the new node will grow too large once it becomes the root node, we will move it down and swap it with the smallest child node until we restore the minimum heap.
A brief explanation of the implementation itself
We will use arrays to implement a fast and space-saving tree structure. I’m not going to get too deep into the math here, but if you’re interested, take a look at this link that explains how math works and why.
Are you ready? Let’s get started.
The design agreement
As always, let’s start by defining what the object is supposed to do for external users. We do this by defining the protocol, and let the concrete classes follow it later. The protocol I designed for the queue is as follows:
Protocol Queue {associatedType DataType: Comparable /** Inserts a new element into the Queue. - Parameter item: indicates the element to be added. - Returned value: Whether the insertion was successful. */ @discardAbleresult func add(_ item: DataType) -> Bool /** Delete the first element. - Return value: removed element. - Throw value: QueueError type error. */ @discardAbleresult func remove() throws -> DataType /** Gets the first element in the queue and removes it from the queue. - Return value: an optional value containing the first element in the queue. */ func dequeue() -> DataType? /** gets the first element in the queue without removing it from the queue. - Return value: an optional value containing the first element in the queue. */ func peek() -> DataType? /** Clear the queue. */ func clear() -> Void }Copy the codeThe protocol specifies the functionality we need to implement for external users to invoke. The protocol also states that one of these methods may throw an error, and we know from the documentation that it will be of type QueueError, so we need to implement it as well.
enum QueueError: Error {
case noSuchItem(String)
}
Copy the codeThis code is very succinct: we throw an error like the one above when the user tries to remove an element from an empty queue. Now that all the preparations are complete, let’s start implementing the queue itself.
Implement priority queues
We’ll start by declaring the PriorityQueue class, then implement its initialization methods and store elements, along with some “better to have” methods. The code looks like this:
/** Implementation of PriorityQueue based on heap data structure. */ class PriorityQueue<DataType: Comparable> {/** Queue storage. */ private var queue: Array<DataType> /** Size of the current queue. */ public var size: Int { return self.queue.count } public init() { self.queue = Array<DataType>() } }Copy the codeAs you may have noticed, we do not currently have a protocol for implementing queues. When we code, we usually want things to remain relatively separate. And hopefully create an overview so we can look it up. Some classes can become very large over time, and one way to get around this is to use extended scope. This way, each extension tends to do only one task (such as following a protocol, handling storage and initialization, or declarations of nested classes), which is much easier to find later. Let’s try this approach here as well. First, we implement a private extension of type Int, which helps us perform some pre-defined index calculations:
private extension Int {
var leftChild: Int {
return (2 * self) + 1
}
var rightChild: Int {
return (2 * self) + 2
}
var parent: Int {
return (self - 1) / 2
}
}
Copy the codeSince it is private access, this extension is only available in the PriorityQueue file. This aggregates the calculations we will use to get the children and parents of a node. This way we can easily get the index of the leftChild node by calling the.leftchild attribute, without having to do a lot of math in the implementation, and so on. Here is our implementation of the Queue protocol:
extension PriorityQueue: Queue { @discardableResult public func add(_ item: DataType) -> Bool { self.queue.append(item) self.heapifyUp(from: self.queue.count - 1) return true } @discardableResult public func remove() throws -> DataType { guard self.queue.count > 0 else { throw QueueError.noSuchItem("Attempt to remove item from an empty queue.") } return self.popAndHeapifyDown() } public func dequeue() -> DataType? { guard self.queue.count > 0 else { return nil } return self.popAndHeapifyDown() } public func peek() -> DataType? {return self.queue.first} public func clear() {self.queue.removeall ()} /** Returns the first element in the queue and restores the minimum heap sort by moving the root element to the end of the queue. - Return value: the first element in the queue. */ private func popAndHeapifyDown() -> DataType { let firstItem = self.queue[0] if self.queue.count == 1 { self.queue.remove(at: 0) return firstItem } self.queue[0] = self.queue.remove(at: Self.queue.count - 1) self.heapifyDown() return firstItem} /** Restore minimum heap sort by moving elements to the queue head. - Parameter index: indicates the index of the element to be moved. */ private func heapifyUp(from index: Int) { var child = index var parent = child.parent while parent >= 0 && self.queue[parent] > self.queue[child] { Swap (parent, with: child) child = parent parent = child.parent}} /** Restores the minimum heap sort of the queue by moving the root element to the end of the queue. */ private func heapifyDown() { var parent = 0 while true { let leftChild = parent.leftChild if leftChild >= self.queue.count { break } let rightChild = parent.rightChild var minChild = leftChild if rightChild < self.queue.count && self.queue[minChild] > self.queue[rightChild] { minChild = rightChild } if self.queue[parent] > self.queue[minChild] {self.swap(parent, with: minChild) parent = minChild} else {break}}} /** Swap the element in the storage at two index positions. - Parameter firstIndex: Index of the first element to be swapped. - Parameter secondIndex: Index of the second element to be swapped. */ private func swap(_ firstIndex: Int, with secondIndex: Int) { let firstItem = self.queue[firstIndex] self.queue[firstIndex] = self.queue[secondIndex] self.queue[secondIndex] = firstItem } }Copy the codeIt’s a bit too much here, you might want to read it again or two. At the top are all the methods we defined earlier in the protocol, and below are some helper methods that are private and only available in this class. I’ve annotated these helper methods so you can quickly see what they do. Also, remember to take a look at how the previous extension to Int is used here. In my opinion, this is a very simple and practical design.
conclusion
We now have all the functionality required for PriorityQueue. Now we’ll add an implementation of the CustomStringConvertible protocol so that we can get something to read when we pass a queue to the print function:
extension PriorityQueue: CustomStringConvertible {
public var description: String {
return self.queue.description
}
}
Copy the codeWow!!!! That’s all for this time. Now you know how to implement a priority queue based on a heap data structure. If you have any questions, please feel free to comment. For more information on iOS development, check out my previous article: Introduction To Protocol Oriented Programming Using Swift Extensions To Clean Up Our Code
This article is translated by SwiftGG translation team and has been authorized to be translated by the authors. Please visit swift.gg for the latest articles.
277 Share/Implementing heap-based priority-queue-using-swift/wechat.
Roc Zhang, APPCODA EDITORIAL TEAM, Chinese Academy of Sciences, Beijing 100049, China Proofreading: PMST, NUMbbbbb; Finalized: Forelax
In computer science, there are many problems that can improve the time complexity of algorithms by implementing the underlying data structures as priority queues. One example is Dijkstra’s shortest path algorithm, which uses priority queues to search a graph for the shortest path between two vertices.
Unfortunately, the default implementation of priority queues is not provided in Swift’s standard library. So we’ll look at how to implement heap-based priority queues ourselves.
If you want to do this together in your own IDE, click here to get the source code.
What is a priority queue?
A priority queue is a data structure that can efficiently sort objects with relative priority. It sorts objects in the queue one by one according to the priority of each object in the queue.
Let’s say you’ve created a series of tasks and are going to run them at some point in the future. Using priority queues can make these tasks perform as you expect.
In the next article, we will use the heap structure to implement our priority queue.
What is a heap?
We can think of a heap as a tree with at most two children per node, but unlike trees, adding new nodes to the heap is done as far to the top left as possible. As shown below:
At the same time, the heap also has some characteristics related to the relative size relationship between nodes. A minimal heap (the one we’re going to use) has the property that each node is smaller than its children. The largest pile is just the opposite.
To be able to maintain this property, we need to do something to get the correct order of nodes. When we insert a new node, we place it in the first free position starting at the top left of the tree. If the minimum heap property is not established after placement, the node is swapped with its parent until the minimum heap property is established. The following figure shows inserting the number 2 into an existing minimum heap.
When moving an object out of the queue, restrict the operation to one end of the queue. We will do this by limiting the deletion of only the root node. When the root node is removed, it is replaced by the top rightmost node. Since there is a high probability that the new node will grow too large once it becomes the root node, we will move it down and swap it with the smallest child node until we restore the minimum heap.
A brief explanation of the implementation itself
We will use arrays to implement a fast and space-saving tree structure. I’m not going to get too deep into the math here, but if you’re interested, take a look at this link that explains how math works and why.
Are you ready? Let’s get started.
The design agreement
As always, let’s start by defining what the object is supposed to do for external users. We do this by defining the protocol, and let the concrete classes follow it later. The protocol I designed for the queue is as follows:
Protocol Queue {associatedType DataType: Comparable /** Inserts a new element into the Queue. - Parameter item: indicates the element to be added. - Returned value: Whether the insertion was successful. */ @discardAbleresult func add(_ item: DataType) -> Bool /** Delete the first element. - Return value: removed element. - Throw value: QueueError type error. */ @discardAbleresult func remove() throws -> DataType /** Gets the first element in the queue and removes it from the queue. - Return value: an optional value containing the first element in the queue. */ func dequeue() -> DataType? /** gets the first element in the queue without removing it from the queue. - Return value: an optional value containing the first element in the queue. */ func peek() -> DataType? /** Clear the queue. */ func clear() -> Void }Copy the codeThe protocol specifies the functionality we need to implement for external users to invoke. The protocol also states that one of these methods may throw an error, and we know from the documentation that it will be of type QueueError, so we need to implement it as well.
enum QueueError: Error {
case noSuchItem(String)
}
Copy the codeThis code is very succinct: we throw an error like the one above when the user tries to remove an element from an empty queue. Now that all the preparations are complete, let’s start implementing the queue itself.
Implement priority queues
We’ll start by declaring the PriorityQueue class, then implement its initialization methods and store elements, along with some “better to have” methods. The code looks like this:
/** Implementation of PriorityQueue based on heap data structure. */ class PriorityQueue<DataType: Comparable> {/** Queue storage. */ private var queue: Array<DataType> /** Size of the current queue. */ public var size: Int { return self.queue.count } public init() { self.queue = Array<DataType>() } }Copy the codeAs you may have noticed, we do not currently have a protocol for implementing queues. When we code, we usually want things to remain relatively separate. And hopefully create an overview so we can look it up. Some classes can become very large over time, and one way to get around this is to use extended scope. This way, each extension tends to do only one task (such as following a protocol, handling storage and initialization, or declarations of nested classes), which is much easier to find later. Let’s try this approach here as well. First, we implement a private extension of type Int, which helps us perform some pre-defined index calculations:
private extension Int {
var leftChild: Int {
return (2 * self) + 1
}
var rightChild: Int {
return (2 * self) + 2
}
var parent: Int {
return (self - 1) / 2
}
}
Copy the codeSince it is private access, this extension is only available in the PriorityQueue file. This aggregates the calculations we will use to get the children and parents of a node. This way we can easily get the index of the leftChild node by calling the.leftchild attribute, without having to do a lot of math in the implementation, and so on. Here is our implementation of the Queue protocol:
extension PriorityQueue: Queue { @discardableResult public func add(_ item: DataType) -> Bool { self.queue.append(item) self.heapifyUp(from: self.queue.count - 1) return true } @discardableResult public func remove() throws -> DataType { guard self.queue.count > 0 else { throw QueueError.noSuchItem("Attempt to remove item from an empty queue.") } return self.popAndHeapifyDown() } public func dequeue() -> DataType? { guard self.queue.count > 0 else { return nil } return self.popAndHeapifyDown() } public func peek() -> DataType? {return self.queue.first} public func clear() {self.queue.removeall ()} /** Returns the first element in the queue and restores the minimum heap sort by moving the root element to the end of the queue. - Return value: the first element in the queue. */ private func popAndHeapifyDown() -> DataType { let firstItem = self.queue[0] if self.queue.count == 1 { self.queue.remove(at: 0) return firstItem } self.queue[0] = self.queue.remove(at: Self.queue.count - 1) self.heapifyDown() return firstItem} /** Restore minimum heap sort by moving elements to the queue head. - Parameter index: indicates the index of the element to be moved. */ private func heapifyUp(from index: Int) { var child = index var parent = child.parent while parent >= 0 && self.queue[parent] > self.queue[child] { Swap (parent, with: child) child = parent parent = child.parent}} /** Restores the minimum heap sort of the queue by moving the root element to the end of the queue. */ private func heapifyDown() { var parent = 0 while true { let leftChild = parent.leftChild if leftChild >= self.queue.count { break } let rightChild = parent.rightChild var minChild = leftChild if rightChild < self.queue.count && self.queue[minChild] > self.queue[rightChild] { minChild = rightChild } if self.queue[parent] > self.queue[minChild] {self.swap(parent, with: minChild) parent = minChild} else {break}}} /** Swap the element in the storage at two index positions. - Parameter firstIndex: Index of the first element to be swapped. - Parameter secondIndex: Index of the second element to be swapped. */ private func swap(_ firstIndex: Int, with secondIndex: Int) { let firstItem = self.queue[firstIndex] self.queue[firstIndex] = self.queue[secondIndex] self.queue[secondIndex] = firstItem } }Copy the codeIt’s a bit too much here, you might want to read it again or two. At the top are all the methods we defined earlier in the protocol, and below are some helper methods that are private and only available in this class. I’ve annotated these helper methods so you can quickly see what they do. Also, remember to take a look at how the previous extension to Int is used here. In my opinion, this is a very simple and practical design.
conclusion
We now have all the functionality required for PriorityQueue. Now we’ll add an implementation of the CustomStringConvertible protocol so that we can get something to read when we pass a queue to the print function:
extension PriorityQueue: CustomStringConvertible {
public var description: String {
return self.queue.description
}
}
Copy the codeWow!!!! That’s all for this time. Now you know how to implement a priority queue based on a heap data structure. If you have any questions, please feel free to comment. For more information on iOS development, check out my previous article: Introduction To Protocol Oriented Programming Using Swift Extensions To Clean Up Our Code
This article is translated by SwiftGG translation team and has been authorized to be translated by the authors. Please visit swift.gg for the latest articles.