A swifty heap implementation: how structs are more performant than classes!

A while back, none of my heap-based solutions written in swift were being accepted on leetcode. I tried a few things to try to optimize the logic, but for the last few test cases, the time limit was exceeding. I was about to ask a question on stackoverflow, but while sharing my heap implementation, I realized my heap was a class. I tried changing it to a struct and boom, my solutions started getting accepted. Most of us have read how structs are faster than classes, but I thought this would be a good example to share to register that fact(It certainly didn’t register in my brain and I went ahead and implemented my heap as a class)

First, let’s talk about the heap data structure a little bit.

As shown below, a heap resembles a binary tree data structure. The heap is a tree, and all of the nodes in the tree have 0, 1, or 2 children.

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, it 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.

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.

Now let me share a snippet of my implementation of a heap in swift as a struct.

Above is a basic implementation we need to build a heap. The init() takes in a priority function which basically decides the priority of the elements in the heap. Notice that the heap above is using generics, since we have an array, the generic type used here is an Element.

Now let’s look at the buildHeap() function. You might be wondering why we are just iterating through the first half of the array. Every level of the heap has room for twice as many elements as the level above, so we can 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. So basically we go through all parent nodes and try to make them heaps by comparing them with their children. And we do this in reverse order starting from the lowest parents and going up towards the root of the heap.

Below is the higherPriority(idx:) function’s implementation. For every parent, we try to figure out if either of its children has a higher priority(children of a parent in a heap lie at index 2*i + 1 and 2*i + 2, if i is the index of the parent). If it does we swap the two indexes and call heapify on the higher priority index.

Now that we have looked at making a heap, let's look at the insert element function.

We just append the element to the end of the array and call siftUp.

Now we need to put this element at its correct position in the heap. SiftUp is kind of the reverse of heapify (which I could’ve named siftDown for context, but I like the term heapify :)). Here we try and find if the parent’s index has a smaller priority, if it does, similar to heapify, we swap the indexes and recurse for the higherPriority index. This way we keep sifting up towards the root, making sure all parents satisfy the heap property.

Now let’s look at how to extract the highest priority element from the heap. We have 2 functions below, the first one is peek(), which gives us the highest priority element of the heap.

The other one is pop(), which not only returns the highest priority element but removes that element from the heap as well. It does that by swapping its value with the last element of the array and removing the last element. Now all that’s left is to heapify the root which has now become the lowest priority element of the heap.

Now that we’re done implementing the heap, let’s look at one of the questions my solution was exceeding time limits when heap was written as a class.
Find Median from Data Stream

The approach to solving this requires us to work with two heaps. The first heap is a max-heap with the maximum element at the top, the second one a min-heap, with the minimum element at the top. Now we distribute the element amongst these in a way that the max heap has the first half of the elements and min-heap the second half of the elements when sorted in increasing order. So if the total count is even, the median is the average of the top of the two heaps and if it's odd, the median is the top of the max-heap as we always make sure max heap has one more element than min-heap if the total number of elements is odd.

Now let’s look at the solution. As shown below we begin by declaring two heaps, a max-heap, and a min-heap. We also define a count variable which lets us know at any point how many total elements have been added.

Below is the addNum function, this is the main function we need to focus on. Let’s look at the conditions

First, we check if the max-heap is empty, if it is, just insert the num there as the maxHeap will always have one more element when the total number of elements is odd.

Second condition checks if the number of elements in both the heaps is equal. If they are we know we need to increase the number of elements in the max heap, as mentioned above if the total number of elements is odd, max-heap has more elements. But we can’t just push the element to the max heap, we need to put the element considering its value, if the number is less equal to the top element of the min-heap, then we can just push it to the max-heap, as the max-heap is supposed to have the smaller half of the elements. If not, we push it to the min-heap, but now min-heap has more elements than max-heap, so we remove the top element from the min-heap (which is also the smallest element in the min-heap) and add it to the max heap, thus retaining the fact that max heap has the smaller half or element and min heap the larger half.

Now, the last condition is where the number of elements is not the same, max-heap has one more element than min-heap. If the min-heap is empty, we check if the element is bigger than max-heap’s top element, we just add it to the min-heap. Else like above, we add it to the max heap and then remove the top element from the max-heap adding it to the min-heap.

Let’s look at the last 2 conditions now, if the number is greater than the top of the min-heap, we just insert it in the min-heap. Else again, we add it to the max-heap and remove the top element from the max-heap adding it to the min-heap, to balance the count.

Here is the findMedian function, it's pretty straightforward, based on the total number of elements being even or odd, we return the median

Here is the link to the complete solution: https://github.com/vabiosd/SwiftyHeap

Now that we have covered the solution, let's talk about structs vs classes. As mentioned at the beginning of the article, I had implemented the heap as a class and was scratching my head seeing my solutions’ time limit being exceeded. But when I converted the heap to a struct, my solutions started getting accepted. Let’s look at why structs are more performant than classes.

Structs are value types and classes are reference types. Value types are stored on the stack and reference types are stored on heaps (actually the reference is stored on the stack while the object it refers to is stored on the heap). Stack is used for static memory allocation and Heap for dynamic memory allocation

NOTE: If the value type instance is part of a class instance, the value is stored in the heap along with the class instance. Since reference types are always stored on the heap, anything they contain (even value types) is also stored on the heap. For example, if a class has a struct instance inside it, then the struct instance will be stored in the heap along with the class instance.

So clearly the difference between the performance of structs and classes lies in the performance of stacks vs heaps.

Stack is tightly managed and optimized by the CPU. When a function creates a variable, the stack stores that variable and is destroyed when the function exits. Variables allocated on the stack are stored directly to the memory and access to this memory is very fast. When a function or a method calls another function which in turn calls another function, the execution of all those functions remains suspended until the very last function returns its value. The stack is always reserved in a LIFO order, the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack, freeing a block from the stack is nothing more than adjusting one pointer. Since the stack is very well organized, it is very efficient and fast.

The system uses the heap to store data referenced by other objects. The heap is generally a large pool of memory from which the system can request and dynamically allocate blocks of memory. The heap doesn’t automatically destroy its object like the stack does. External work has to be done to do this. ARC does the job in apple devices. The reference count is tracked by the ARC and when it becomes zero, the object is deallocated. Hence, the overall process (allocation, tracking the references, and deallocation) is slower compared to stacks. So value types are faster than reference types.

Here’s a great WWDC video explaining the performance aspect of different swift types, I highly recommend watching this: https://developer.apple.com/videos/play/wwdc2016/416.

This post turned out to be much longer than I expected, but I hope you guys found some useful info in there. Please do let me know if something was unclear or you guys have a better way of implementing a swifty heap or solving problems like the median of a number stream. Thanks for reading!