Let's write an inplace Heapsort in Swift
Using only extensions, learn how to implement a inplace heapsort, and order your lists in O(n log n).
I was really interested on this problem of sorting elements. Sorting with heapsort is fast! But it has a big problem: conventionally you have to build a heap to use a heap sort. In a real world usually you don't have a heap mounted to sort whenever. I just imagined that we could create a heapsort inplace, and instead of dealing with heaps objects, we could still have our simple array, and only transform it in a heap when needed.
First of all, I hope you understand what is a heap, and how the heapsort works. If not, I wrote those two pieces that are potentially a good start to understand this structure and sorting algorithm.
The procedures to create a inplace heapsort
The process will be simple. We'll have a list, we'll transform that list in a heap, and then we'll apply the heapsort. The good news is we'll still use just loops to build these guys, leaving aside any recursive call.
In a quick analysis, the list will be transformed into a heap in O(n log n), the heap will be sorted in O(n log n). So we basically keep our computational complexity. What is good for us, seems that this inplace heapsort will be useful.
Transforming the list in a heap
First of all, I will give you guys a couple methods that we'll use as tools during the process of creating this heapsort. They won't need much explanation, most part of them appeared on previous pieces I posted, and they're super simple.
Now we focus in the first part of the process: To transform a list in a heap. Remember, we'll do everything in a extension, so any call to self will be in fact a reference for the list will be manipulating.
An array with less than 2 elements is intrinsically sorted. If this is our case, we don't have to do any work.
Now what we will do is go over the array transforming it in a heap. The method we're doing here is very similar to a heapifyUp: We get each element of the list, after the parent node, and we check if this element is in the right place. We do it by comparing it with its parent. If this element is bigger than it's parent we swap them. And now we do the same procedure with its parent. This procedure will be repeated till we get to the top of the list (root) or till we find a parent that's actually bigger than the child being compared. After doing it with all the elements, we'll have a heap (max in this case).
Sorting the heap
Since now we have a heap with no need of creating a extra extructure, we now just have to apply the heapsort. But it would be really nice if we could do it in our extension. Let's see the approach used.
We'll use an iterator from L-1 to 1, where L = A.size, and A being our list. We basically do this inverse for to save computation with the i that you can notice being used around the code.
The idea of the heapsort is to swap the first element of the list with the element at index i in this case. That's because we know that A[0] is the biggest element in an max-heap, so it's supposed to be at the end of our array. After doing this exchange, we have to make sure that the element at the root or top (index 0) is positioned in the right place. In order to do it, we'll compare it with its children and swap around to find a smaller children that the node being compared. We call this method heapifyDown.
At the end of this process, we'll have a inplace heapsort. I will leave this code in my GitHub if you're interest on applying it somewhere, debug, or anything.
Leave a comment if you liked this piece. See you soon!
