iOS

Implementing a Heap Based Priority Queue Using Swift


There is a wealth of problems in computer science where using a priority queue as your underlying data structure can greatly improve the time complexity of your algorithm. One example is Dijkstra’s Shortest Path Algorithm, where a priority queue is used to search a graph for the shortest path between two vertices.

Editor’s note: This is the first tutorial of our Swift Algorithm series. If you want to see more tutorial like this, please leave us comment below to let us know.

Sadly, Swifts standard library does not come with a default implementation of a priority queue, so we are going to look into how we can implement a heap based priority queue on our own.

To follow along in your own IDE, you can get the source code by clicking on this link!

What Is A Priority Queue?

A priority queue is a data structure that allows for efficient sorting of objects with a relative priority. You can throw a bunch of objects into the queue and it will hand them back, one by one, based on how important they are compared to each other.

Let’s say that you have created a bunch of tasks for your computer to run at some specific point in the future. Adding them to a priority queue will let your computer dequeue the tasks and get the objects that are due for execution before the ones that are still waiting for their deadline.

To implement our queue, we are going to use a heap structure!

What Is A Heap?

Think of a heap as being a tree, where each node has at most 2 children. A heap also comes with the restriction that it needs to add all new nodes to the top level, as far to the left as possible. Take a look at the following image:

Implementing a Heap Based Priority Queue Using Swift 1

A heap also maintains a property relating to the relative size of each node. A min heap (which is the one we’re going to use) maintains the property that each node is smaller than both of its child nodes, whereas a max heap goes the other way around.

To be able to maintain this property, we’re going to need to do some manipulations to get the correct ordering of nodes. When we insert a new node, we are going to add it to the first available spot from the left in the top level of the tree. If the min heap property does not hold when this is done, we will start swapping the node with its parent until we reach a state where we once again have a min heap. The image below will show you what happens when we insert the number 2 into an already existing min heap:

Implementing a Heap Based Priority Queue Using Swift 2

When we dequeue (or remove, for that matter) an object from our queue, we will limit ourselves to doing so from one end. We are going to implement this in a way that you can only ever remove the root element. When that element is removed, it is replaced by the rightmost element at the top level of our tree. Since that new element will almost certainly be too big to stay in the root, we will move it downwards, swapping it with the smallest child until we have restored our min heap.

A Quick Note About The Implementation Itself

We are going to use an array to make a lightning fast and space efficient implementation of this tree structure. I am not going to go into too much detail about the mathematics of it, but if you’re interested, you can check out this link that explains exactly how and why the maths look like they do.

All set? Let’s go!

Designing The Protocol

As always, we need to start by defining what kind of functionality our object should present to an outside user. We do this by declaring a protocol that our class will later conform to. For our queue, I’ve declared the following Queue protocol:

This protocol specifies exactly what outside users can expect from the queue that we are going to implement. This protocol also specifies that one of the methods may throw, and the documentation tells us that it will throw an error of type QueueError, so we’re going to have to implement that as well!

This one is short and to the point. In case the user tries to remove an item from an empty queue, we are going to throw this error.

Now that the preparations are done, let’s get to the queue itself.

Implementing The Priority Queue

We are going to start by declaring our PriorityQueue class and implement initializers and our backing storage, as well as some nice-to-have methods. The code is going to look like this:

You may notice that we’re not even touching the Queue protocol here. When coding anything, we usually want to keep things separated from each other. We want to create an overview and know where to find the things we’re looking for. Some classes tend to get kind of big, and one way to deal with that is to implement the class using extension scopes. That way, each extension will tend to one task (like conforming to a protocol, handling backing storage and initializing, or declaring a nested class) and things will be much easier to find later. Let’s try that here, by first implementing a private Int extension that performs some predefined index calculations for us:

This extension will only be available from within our PriorityQueue file, due to the private access control. What it does is that it collects some of the calculations that we are going to use to get the children and parents of a specific node. Instead of doing a bunch of math in our implementations, we can call the .leftChild property to get the left child index, and so on.

Let’s get to the Queue protocol conformance. It looks like this:

This one gets a little bit bigger, so you may want to read it one or two more times. On top are all the protocol methods that we specified earlier, and below them are private helper functions that will only be available inside this particular class. I’ve documented the helper methods so that you can get a quick overview of what they’re doing. Also, take a look at how the Int extensions are used in this implementation. Pretty neat functionality to have, if I may say so myself!

Wrapping up

Now, that’s all the functionality we need for our PriorityQueue. We’re going to add conformance to the CustomStringConvertible protocol, just to be able to pass a queue into the print function and actually get something readable back:

Sweet!

That’s it for this time! Now you know how to implement a priority queue based on a heap data structure. Feel free to comment if you have questions.

To learn more about iOS Development, check out my previous articles:

This is a guest post by Jimmy M Andersson. The article was first published on Medium.

About the Author: Jimmy M Andersson, a software developer working with data acquisition at a company named NIRA Dynamics, active in the automotive industry. He develops monitoring and logging applications that demonstrate and visualize his companies product portfolio and its functionalities. Currently, he is also working his way towards a masters degree in Information Technology, where his aim is to graduate with a major in Data Science. He writes weekly software development articles on Medium.

Twitter : https://twitter.com/jimmymanderssonEmail: [email protected].

Tutorial
Building a Message Sticker App Extension in Xcode 8
Tutorial
A Beginner’s Guide to Auto Layout with Xcode 10
iOS
Introduction to Auto Layout
There are currently no comments.

Shares