#heapsort

Named for Arabic mathematician al-Khwarizmi and partially formalized by queer mathematician Alan Turing, algorithms are simply a process for doing things, potentially with a desired result.

An early algorithm we learn in school is how to add two whole numbers together.  Using pencil and paper, you can probably figure out what 420 + 69 is.  In fact there are multiple ways.  You could draw out 420 dots, draw another 69 dots, and count how many there are in total.  Or you could lay them vertically, start at the ones column, and compute the digits of the sum.

Algorithms are not strictly related to numbers.  What if you’re a teacher and you want to sort homework assignments alphabetically by the students’ names?  Well you’ll probably have a process, which involves checking repeatedly if two pieces of homework are out of order (e.g. if you had homework from Bob then homework from Alice, you would swap the two since Alice is first alphabetically).

Another great non-numerical example of algorithms is solving the Rubik’s Cube and it’s larger variants.  In the cube solving community, there are algorithms for specific processes, such as rotating corners cubies or flipping edge cubies.  Some of these apply to the 3x3x3 cube, others can be generalized to help one solve a 69x69x69 cube.

Algorithms are also beautiful.  Visualizing how the data dances around can be incredible.  Check out this animation from Wikipedia showing the Heapsort algorithm in action:

This inspired the hell outta me when I first saw it in 2007.  That diagram a couple seconds in, where it just sounds like it’s emitting a thunky beep at ya before suddenly just putting everything together.  The way there’s sort of a pattern before it.  Just that sheer magic.

You can also make art out of algorithms.  From my username, one of my favorite categories is maze generation algorithms.  Think Labyrinth, whose algorithm page I just linked, was an early website I found on the Internet, and I’m so happy it has survived the various eras of web evolution.  The Maze of Theseus in particular was a huge inspiration for me after printing it out in 2000 on a summer road trip.

Alas Think Labyrinth is from before the days of heavy animations on the Internet, so to visualize a maze algorithm I will instead link to Mike Bostock’s article on Visualizing Algorithms.  It includes many dynamic animations that are rendered in your browser, including the sorting algorithms and maze generation algorithms mentioned above, among many others.

So why the hate for algorithms?

On Tumblr in the past few days, and more generally social media in the past decade, we recently saw favoritism for sorting algorithms that allow us to view our feeds in chronological order.  Many claimed they were opposed to an algorithm that decided in a corporate-specific manner what we should see first.  Let me be clear:  the corporate ordering of a feed is bad, but it is not bad because it’s an algorithm.  It’s bad because it’s not one of the algorithms that users want for ordering their feed.

The other negative use case grew heavily in the past 15 years:  algorithms that are “trained” on biased and/or unethically obtained data.  We’ve seen many examples of systems that were trained on data sets of white college students such as facial recognition technology, which then later gets implemented at a large scale and fucks over people of color.  The past couple years we’ve seen a rise in creating data sets based on scraping millions of artists’ works without any permission from the artists themselves*.  Either of these applied to a corporate or government scale leads to active harm to populations already at risk and probably some new ones too.

Finally, we’ve seen a rise in computer automation for things that should be done by people.  I can’t find the specifics, but this quote is allegedly from a 1979 IBM presentation:

A computer can never be held accountable, therefore a computer must never make a management decision.

My first thought on where this comes up is applying for jobs.  Many companies will use a poorly thought out algorithm to filter through job applications, simply scanning for a couple key words they want (programmers who know Vulkan or Node.js) or more maliciously looking for words they don’t want (needing any kind of accommodation, sounding too anti-capitalist, etc).  These algorithms cannot be held accountable and should not be involved in any stage of the hiring process.

Quick aside:  When I was searching for the source of that quote about accountability, I typed in the first half in Google, and the autocomplete was

Fucking modern Google.

Some concluding thoughts

I like algorithms.  They are a passion of mine.  When people say algorithms are evil, I’m sad.  When people recognize the usage of certain algorithms in certain contexts are evil, I’m more happy (yet still disturbed these things happen).  I just really wanted to educate people on the usage of the word.

Also, algorithms are not about Al Gore’s dance moves.  Please stop with that stupid fucking joke.

*I mentioned scraping data from millions of images without permission of the creators.  My one iffy status with this is how sort of applies to the human brain doing a similar process over the span of one’s life.  What is it that separates my looking through a book of Escher’s works from a computer looking at it?

Yesterday I implemented (in JavaScript) versions of mergesort, quicksort, and heapsort--some of sorting algorithms' greatest hits. In most standard sorting problems these algorithms are the fastest available, having a time complexity O(nlogn).

Quicksort

Quicksort is trivial to implement when one doesn't care about extra memory usage--just make lessThanPivot and greaterThanPivot arrays at each level of recursion and return quickSort(lessThanPivot).concat(pivot).concat(quicksSort(greaterThanPivot). But to implement it in such a way that the space complexity is O(logn) is less trivial. It is possible to pass the original array up the recursion stack along with left and right pointers. These pointers will index the start and end of the current partition being operated on. Using an in-place quicksort will, of course, sort the array in place, such that the original (pre-sort) ordering will be lost.

Heapsort

Heapsort is even less trivial to implement in-place, but its greatest advantage over its rival quicksort is an in-place implementation--this is what allows it to achieve an incredible O(1) space complexity. The trivial waiy to implement heapsort is to write a Heap class and repeatedly call removeMin on the Heap instance, pushing the return value into a sorted array. This of course uses O(n) space for the sorted array.

Since an array may be used as the underlying data structure of a Heap, there is a clever way to do all of the heapifying in that array (please google "heapify" for a detailed explanation of what that is). The idea is first to, rather than building a Heap data structure, "build the heap" by heapifying-up within the unsorted array (such that the unsorted array is now a valid representation of a heap) and, second, to perform a similarly-modified heapify-down within the unsorted array/heap-representation.

The modified heapify-down function is the heart of the algorithm. Instead of removing the minimum from a heap, this modified function places the element at the end of the array, while also keeping track of the part of the array which has now been sorted. The last element "in the heap" thus gets closer and closer to index 0, while the sorted portion of the array grows with every iteration. Since the heapify-up and heapify-down functions are both O(logn), we get an overall time complexity of 0(nlogn) because we have to perform each n times. The benefit of implementing heapsort this way rather than the trivial way using a Heap is of course that now all we are keeping track of is a couple of pointers, achieving O(1) space complexity!

Considerations

Quicksort turns out to be the quickest of the sorts primarily due to its exceptional cache performance. The order in which it reads elements into memory is optimized for sequential reads. Heapsort, on the other hand, jumps around continuously, having to repeatedly read/write to child/parent indices that could be as far as n/2 elements away (where n is the number of elements). Quicksort has the downside, though, that its worstcase time complexity is O(n**2), though with randomly-picked pivots this possibility is highly unlikely (we would need to repeatedly pick all the smallest remaining element as the pivot, or repeatedly pick the largest).

Aren't descriptions of heaps hard to follow? Let's see if we can do better by shamelessly taking notes from the Wikipedia page.

Binary heaps: nodes have two children (it's a binary tree).

** d-ary heaps:** May be faster in practice due to memory caching.

Shape property: all levels of the tree are filled except possibly the leaf level, which is filled from left to right. This means it's a complete binary (or d-ary) tree.

Heap property: a node dominates (is smaller/larger than, depending on the type of heap) all of its children. This doesn't mean the heap is stratified, because a c-command (aunt-niece) relationship could be out of order. It's like family trees: you're likely to be older than your nieces and nephews, but you don't have to be. But you have to be older than your sons and daughters.

One way to remember how the heap operations work is that they always make the heap satisfy the shape property first, then the heap property.

The insert and delete operations move nodes vertically in the tree, and because the height of the tree is log(n), these operations are O(log n).

Insert: You insert into the bottom, in the next empty leaf slot, and then bubble up. Bubbling up means swapping a node with its parent until it gets a parent that dominates it. (Not the first time talking about trees has sounded disturbing, won't be the last.)

Delete: When you delete, you delete the root (min or max), because that's what heaps are for. Then you take a leaf, put it at the root, and bubble down. Bubbling down means swapping a node with its child, the one that dominates it the most, until it dominates both of its children.

Create: Creating a heap naively is n insertions at O(log n) each, so O(nlogn). But you can do it in a way that converges to O(n).

Do the first half of the insert operation on every node - add leaves, but don't bubble up. This makes a binary tree that satisfies the shape property but not the heap property.

Instead of bubbling everything up the whole tree, bubble everything down the sub-tree it is the root of. Start at the leaves and work your way up. Since most subtrees are very short, this turns out to be fast. This way of turning a complete binary tree into a heap is called heapify.

Implementation

In an effort to make our lives harder, or save space or something, heaps are often implemented as arrays where you just know due to the shape property which things are parents of which. Worse, some people start this array at 0, and some start it at 1.

If your root is at 0, and you have the arbitrary node at index i, its parent is at floor((i-1)/2) and its children are at 2i + 1 and 2i + 2.

If your root is at 1, i's parent is at floor(i/2) and its children are at 2i and 2i + 1.

Our reward for dealing with this is that heapsort can operate in place on an array.

Heapsort