Swift Heap/Priority Queue
Recently I was developing a scheduler in Swift and came across the fact that Swift does not provide a priority queue. So, then I looked up what it took to implement a priority queue which lead me to the heap implementation. The reason the heap implementation is interesting is because it gives a Big O Notation of O(1) for getting the top element and a O(log n) on insert and remove. As it turns out, implementation is very easy and maybe that is why there is not a default implementation. First, let’s start with a picture of the implementation:
Above you can see the tree and how it is represented in an array. So, this means there are a couple of properties to our array that make it a heap or graph. We have a pattern of node, left leaf, right leaf, left leaf of left…. This means that:
the parent can be found by :
parent = (index-1)/2
So, for left leaf (19 in the figure above) it would be (1–1)/2 is our parent. For left leaf of left (17 in the figure above), it would be (3–1)/2 or index 1.
the reverse can be used to find the children:
left = index * 2+1
right=index*2+2
So, using these simple rules, we can create a heap in Swift like this:
A couple of things to note: I haven’t set everything private for demonstration purposes. Also, this heap keeps the array and maintains its count. Since we set the first element as the last element during delete, we can also safely call remove on the last element of the array at no cost (i.e. no shift necessary).
So, the above code achieves a heap queue that always returns the top most item based on the comparator. We could easily flip around our comparator and create a min heap. As you can see, we achieve our O(log n) where n is the length of the array heap in our Heap class. Getting the top element is O(1). The insert is essentially adding something to the end and then walking up its parent to find the right spot and since the parent is halved every time, we will get at most a log n times of walking.
The same is true for the removal, we replace the top with the bottom and then rebalance the tree.
I hope this helps you to either use the priority queue or create your own. The priority queue or heaps can be useful for both backend and frontend Swift. Happy Coding!
