Swift Algorithm Club: Heap and Priority Queue Data Structure

One last first thing

The only essential thing left to do is to check the Heap‘s initializer. Because the Heap is a struct, it comes with a default init function, which you can call like this:

var heap = Heap(elements: [3, 2, 8, 5, 0], priorityFunction: >)

Swift’s generic inference will assume that heap has a type of Heap, and the comparison operator > will make it a maxheap, prioritizing higher values over lower values.

But there’s a danger here. Can you spot it?

[spoiler]The elements array isn’t ordered. You’ll have to create an explicit init function which does some initial prioritizing of elements.[/spoiler]

Write this function at the beginning of the Heap struct, just below the two properties.

init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) { // 1 // 2
  self.elements = elements
  self.priorityFunction = priorityFunction // 3
  buildHeap() // 4
}

mutating func buildHeap() {
  for index in (0 ..< count / 2).reversed() { // 5
    siftDown(elementAtIndex: index) // 6
  }
}

Let's review these two functions.

1. First, you've written an explicit init function which takes an array of elements and a priority function, just as before. However, you've also specified that by default the array of elements is empty, so the caller can initialise a Heap with just the priority function if they so choose.
2. You also had to explicitly specify that the priority function is @escaping, because the struct will hold onto it after this function is complete.
3. Now you explicitly assign the arguments to the Heap's properties.
4. You finish off the init() function by building the heap, putting it in priority order.
5. In the buildHeap() function, you iterate through the first half of the array in reverse order. If you remember that the every level of the heap has room for twice as many elements as the level above, you can also work out that every level of the heap has one more element than every level above it combined, so the first half of the heap is actually every parent node in the heap.
6. One by one, you sift every parent node down into its children. In turn this will sift the high priority children towards the root.

And that's it. You wrote a heap in Swift!

A final thought

Let me leave you with a final thought.

What would happen if you had a huge, populated heap full of prioritised elements, and you kept dequeueing the highest priority element until the heap was empty?

You would dequeue every element in priority order. The elements would be perfectly sorted by their priority.

That's the heapsort algorithm!

Where To Go From Here?

I hope you enjoyed this tutorial on making a heap data structure!

Here is a Swift playground with the above code. You can also find alternative implementations and further discussion in the Heap section of the Swift Algorithm Club repository.

This was just one of the many algorithms in the Swift Algorithm Club repository. If you're interested in more, check out the repo.

It's in your best interest to know about algorithms and data structures - they're solutions to many real world problems, and are frequently asked as interview questions. Plus it's fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing trees in Swift, please join the forum discussion below!

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.