Swift Data Structures: Heap
What is a Heap?
The Heap is a really neat data structure which allows for the prioritization of minimum or maximum values. It is somewhat similar to a Tree in how it’s structured with layers and nodes however it can be easily stored in an Array because it is linear in nature.
For you visual people, this is what a Heap looks like if we were to draw it out:
The above photo shows a Min (Minimum) Heap which prioritizes the smallest value in the data set at the top as the root parent node. Below, there are the nodes with the values 3 and 8 which exist as the left and right child of the parent node with the value 2 above.
The node with a value of 3 has a left child of 4 and a right child of 7. This process goes on and on until all values in the data set in question have been laid out. Note that the values generally increase as you go from top to bottom. They’re not organized from left to right per-se, but they are organized by row.
Row 1 contains the value 2 in the root node’s place. Row 2 has the left and right child nodes with the values 3 and 8 which are both larger than 2. Row 3 contains the left and right child nodes for both nodes 3 and 8. As you can see, both nodes’ children are larger in value. I hope you’re starting to notice a pattern.
Every parent in a Min Heap can have 0, 1, or 2 children – all of which are greater in value than the parent. A Max Heap works in exactly the opposite way.
A heap utilizes an index system like an array to determine the order of values and their place in the Heap starting at the index 0 and counting up. If we’re referring to our visual Heap diagram from earlier, the indexes increment from top to bottom and left to right like so:
How does a Heap work?
The examples you’ve seen so far all have displayed static data. We haven’t added or removed any of the items, however it is of utmost importance that we can change the data in our Heap— otherwise this data structure is worthless. In Swift, we’re going to begin by creating a struct called MinHeap like so:
This struct has an array of type Int which will hold our Heap’s values. But we want to be able to get the index of any node in our Heap, check whether a parent node has a child and vice-versa, and return the actual value of an item at a particular index. Add in the following functions below the items array:
These functions are all private and will be a great help to the functions we’re about to write.
If you’re aware of the way that a Stack works, peek(), pop(), & push() are the functions available (in general) for you to modify the Stack. A Heap utilizes similar public functions for a developer to access and modify the data stored inside: peek(), poll(), and add(). Let’s discuss each below:
Function 1: peek()
The function peek() returns the value of the parent node in the Heap. Depending on whether your Heap is a Min Heap or Max Heap, you’ll be getting back the minimum or maximum value. The Heap’s data is not modified. Add the following at the bottom of the MinHeap struct:
Function 2: poll()
The function poll() returns and removes the value of the parent node from the Heap. Then, private functions within the Heap are called which rearrange the values in the Heap so that the next smallest (or largest) value becomes the parent node at the top and all others fit in to the place they should. Behind the scenes, we’re setting the value of the first item to be the value of the last item in the heap, then removing the duplicate last item. We then “Heapify Down” to check that the value of the root node fits. If it doesn’t, we swap it until it fits. Then we verify that all other indices are in their proper place and swap them accordingly. The Heap’s data is modified. Add the following at the bottom of the MinHeap struct:
You’ll see an error regarding the function heapifyDown(). This is because we’ve yet to write that function. But don’t worry, young grasshopper, we will. 🦗 Also, note that the function utilizes the mutating keyword at the front. Since a struct is a value type, it’s supposed to be immutable – hence why we need to tell the Swift compiler that we want to mutate its’ data.
Function 3: add()
The function add() appends a new value to the end of the Heap (via the items array), then private functions are called which help determine where the new value should go in comparison with existing Heap values. We will call this “Heapifying Up” in the instance of a Min Heap. The Heap’s data is modified in this function as well. Add the following at the bottom of the MinHeap struct:
You will see a similar error regarding the function heapifyUp() like in the function above. Nothing to worry about – we will get there.
What’s going on behind the scenes?
So we have some fancy private functions which help to get the indices and values of the parent, left, and right child nodes. But what good are those functions if they’re never called. They are swap(), heapifyUp(), & heapifyDown(). Let’s dive into how these work as well.
Function 1: swap()
The function swap() does exactly what you’d expect it to do: it swaps the place of two items at particular indices. We will save the value of the first item into a constant, then set itemOne to be equal to theitemTwo we pass in. Then we set the value of itemTwo to the constant we saved first. Add the following at the bottom of the MinHeap struct:
Function 2: heapifyUp()
The function heapifyUp() allows us to help a new value added to the bottom of the Heap find its’ place. We begin by creating a variable called index and using items.count — 1 to get the index of the last item because, you know, zero-indexing. Once we’ve set the index, we start a while loop that will run assuming the new item in the Heap has a parent (which it does). We also check that the value of the parent is greater than the last item. If that is the case, for a Min Heap, we call swap to switch the place of the child and parent. We then set the index variable to be the parent index of the current item in question. Add the following at the bottom of the MinHeap struct:
Function 3: heapifyDown()
The function heapifyDown() begins by setting an variable called index to have a value of 0. The index variable is passed into a while loop which verifies that the item at that index has a left child. We do this instead of checking for a right child since a Heap’s indices go from top to bottom and left to right. A parent node will never have a right child without also having a left child. Entering into our while loop and assuming that the item at the index in question has a left child, we create a variable called smallerChildIndex to be equal to the left child’s index since it’s the smaller of the two child indexes. Then, we check if our parent node has a right child and if the value of the right child is less than the left child we set smallerChildIndex to be equal to the right child’s index. The reason for this will become apparent soon.
After setting this property for either the left or right child, we check if the value of the current parent node is less than the item at the smallerChildIndex. If it is, we break and end the while loop. Otherwise, we swap the values of the two nodes, helping the value go down in the Heap where it should be. After swapping, we set the current index in question to be smallerChildIndex and the process continues until the value is in its’ proper place. Add the following at the bottom of the MinHeap struct:
Interacting with our Heap
We’re now finished with building our Heap in Swift, but what can we do with it? Beneath the MinHeap declaration, create an instance of MinHeap , add in some values, then call dump() passing in myHeap.items like so:
You should see the following print out in the console:
▿ 7 elements
- 2
- 7
- 3
- 10
- 9
- 8
- 4The order of this stack of values might seem confusing at first, but our Heap is working perfectly. 👌 If you remember that the order is going from top to bottom with an index starting at 0, we can draw our Heap like so:
Following the rules of the Heap, you can see that each row going from top to bottom gets progressively larger in general and each parent node has children larger than itself.
Calling peek() returns a value of 2 as you’d expect and calling poll() rearranges the Heap after removing the first item. To see this in action add the following code to the bottom of the MinHeap struct, then call dump(myHeap.items) again:
You should see an entirely re-arranged, but still correct Heap:
▿ 6 elements
- 3
- 7
- 4
- 10
- 9
- 8Here is the Heap visualized:
We did it! We have now successfully built a Minimum Heap which prioritizes the smallest value passed in. When a value is removed, the Heap is reordered so the next smallest value is at the top. But where could this be used in the real world?
Get the full source code here on Github Gist: https://gist.github.com/kalub92/d269ba6b2bf05ca7dcbaae64b4ff7a2d
How could a Heap be useful?
Imagine that you are building a patient intake system for a pediatric emergency room. The hospital wants to prioritize the youngest patients as they come in so that they can recieve care the quickest. Imagine there are a few 6, 7, and 8-year-old kids out in the waiting room, but a very sick 1-year-old enters the waiting room and goes through the intake process. Time-wise, the 1-year-old should be 4th in line, but this hospital wants to give care to the youngest patients first. If a Heap was utilized in the patient intake program, the 1-year-old would go right in to meet with a pediatrician. This is one specific use case, but I want to know your thoughts.
Where do you think a Heap could be implemented usefully in the real world. Comment below and let us know!
If you’re ready to join us and learn more about Swift, Data Structures, & iOS Development, check out Devslopes and enroll in our Apple slope to learn all the skills you need to build your own apps and launch your own app-based startup.
