Swift Algorithm Club: Heap and Priority Queue Data Structure

In this Swift Algorithm Club tutorial, you’ll learn how to implement a heap in Swift 3, a way to implement a priority queue. By Ross O'Brien.

Leave a rating/review
Save for later
Share

The Swift Algorithm Club is an open source project on implementing data structures and algorithms in Swift.

Every month, Kelvin Lau, Vincent Ngo and I feature a cool data structure or algorithm from the club in a tutorial on this site. If you want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll learn how to implement a heap in Swift 3. A heap is frequently used to implement a priority queue.

The Heap data structure was first implemented for the Swift Algorithm Club by Kevin Randrup, and has been presented here for tutorial form.

You won’t need to have done any other tutorials to understand this one, but it might help to read the tutorials for the Tree and Queue data structures, and be familiar with their terminology.

Getting Started

The heap data structure was first introduced by J. W. J. Williams in 1964 as a data structure for the heapsort sorting algorithm.

In theory, the heap resembles the binary tree data structure (similar to the Binary Search Tree). The heap is a tree, and all of the nodes in the tree have 0, 1 or 2 children.

Here’s what it looks like:

Technical Image 1: Illustration of Heap

Elements in a heap are partially sorted by their priority. Every node in the tree has a higher priority than its children. There are two different ways values can represent priorities:

  • maxheaps: Elements with a higher value represent higher priority.
  • minheaps: Elements with a lower value represent higher priority.

The heap also has a compact height. If you think of the heap as having levels, like this:

Technical Image 2: Illustration of levels

…then the heap has the fewest possible number of levels to contain all its nodes. Before a new level can be added, all the existing levels must be full.

Whenever we add nodes to a heap, we add them in the leftmost possible position in the incomplete level.

Technical Image 3: Illustration of adding nodes

Whenever we remove nodes from a heap, we remove the rightmost node from the lowest level.

Removing the highest priority element

The heap is useful as a priority queue because the root node of the tree contains the element with the highest priority in the heap.

However, simply removing the root node would not leave behind a heap. Or rather, it would leave two heaps!

Technical image 4: two heaps

Instead, we swap the root node with the last node in the heap. Then we remove it:

Technical image 5: swapped nodes

Then, we compare the new root node to each of its children, and swap it with whichever child has the highest priority.

Technical image 6: sifting down

Now the new root node is the node with the highest priority in the tree, but the heap might not be ordered yet. We compare the new child node with its children again, and swap it with the child with the highest priority.

Technical image 7: sifting down

We keep sifting down until either the former last element has a higher priority than its children, or it becomes a leaf node. Since every node once again has a higher priority than its children, the heap quality of the tree is restored.

Adding a new element

Adding a new element uses a very similar technique. First we add the new element at the left-most position in the incomplete level of the heap:

Technical image 8: new element

Then we compare the priority of the new element to its parent, and if it has a higher priority, we sift up.

Technical image 9: sifting up

We keep sifting up until the new element has a lower priority than its parent, or it becomes the root of the heap.

Technical image 10: sifting up

And once again, the ordering of the heap is preserved.

Practical Representation

If you’ve worked through the Binary Search Tree tutorial, it might surprise you to learn the heap data structure doesn’t have a Node data type to contain its element and links to its children. Under the hood, the heap data structure is actually an array!

Every node in the heap is assigned an index. We start by assigning 0 to the root node, and then we iterate down through the levels, counting each node from left to right:

Technical image 11: indexed tree

If we then used those indices to make an array, with each element stored in its indexed position, it would look like this:

Technical image 12: the array

A bit of clever math now connects each node to its children. Notice how each level of the tree has twice as many nodes as the level above it. We have a little formula for calculating the child indices of any node.

Given the node at index i, its left child node can be found at index 2i + 1 and its right child node can be found at index 2i + 2.

Technical image 13: all nodes pointing to their children

This is why it’s important for the heap to be a compact tree, and why we add each new element to the leftmost position: we’re actually adding new elements to an array, and we can’t leave any gaps.

Note: This array isn’t sorted. As you may have noticed from the above diagrams, the only relationships between nodes that the heap cares about are that parents have a higher priority than their children. The heap doesn’t care which of the left child and right child have higher priority. A node which is closer to the root node isn’t always of higher priority than a node which is further away.

Implementing a Swift Heap

That’s all the theory. Let’s start coding.

Start by creating a new Swift playground, and add the following struct declaration:

struct Heap<Element> {
  var elements : [Element]
  let priorityFunction : (Element, Element) -> Bool

  // TODO: priority queue functions
  // TODO: helper functions
}

You’ve declared a struct named Heap. The syntax declares this to be a generic struct that allows it to infer its own type information at the call site.

The Heap has two properties: an array of Element types, and a priority function. The function takes two Elements and returns true if the first has a higher priority than the second.

You’ve also left some space for the priority queue functions – adding a new element, and removing the highest priority element, as described above – and for helper functions, to help keep your code clear and readable.