Sorting, Part 2

Heaps of Fun

By Matt Neuburg

Matt Neuburg is the author of REALbasic: The Definitive Guide, and a member of the editorial board of REALbasic Developer. This article was originally published in REALbasic Developer Issue 1.3 (Dec/Jan 2002-3).

Cast your mind back to the last issue of REALbasic Developer, when this column described Bubblesort, an easily understood but prohibitively slow sorting algorithm. We also saw that, when the items to be sorted are objects, it makes sense to embed in the items themselves the knowledge of how their relative ordering works: for maximum generality, we had our objects implement the ComparableThing class interface, so that we could then send any object the ShouldSwapWith message, along with some other object as parameter, to learn whether the first object is, on its own terms, “less than” the second.

In this issue’s column we’ll develop a better sorting algorithm. You might expect, if you’re familiar with these matters, that this would be the popular Quicksort; but instead I’ve elected to talk about Heapsort. There are two reasons for this choice. First, Quicksort, though faster than Heapsort in the best cases, is complicated to implement in a way that is always fast; in fact, in the worst case it can be as slow as Bubblesort, while Heapsort’s speed remains consistent. Also, Heapsort depends upon a secondary notion, the heap, which is intriguing in its own right. (Another interesting sorting algorithm, Shell sort, is shown on p. 162 of my book.)

Here are some definitions to get us started. A binary tree is a data structure where items play the roles of “parent” and “children”, such that (1) every item has one parent except for a single item that has none (the top of the tree), and (2) every item has at most two children. Figure 1 makes the notion clear. It shows a tree made up of the letters from the sentence “this is a tree.” The initial “T” is placed as the top of the tree, with no parent; all other letters have a parent, and no parent has more than two children.

picture
Figure 1: A binary tree

A heap is a binary tree where no parent is smaller (on whatever definition is appropriate) than either of its children. For example, using alphabetical order, the tree in Figure 1 is not a heap, because on the right side of the diagram, an “I” is the parent of an “S”, but “I” is smaller than “S”.

It seems intuitively obvious that if a tree is a heap, its items are essentially sorted. For example, Figure 2 shows a heap, and you can probably sense that to gather up its items in order from largest to smallest would be fairly simple. The details remain to be worked out, and we’ll have to specify the process later on, but the problem doesn’t look difficult on its face.

picture
Figure 2: A heap

Well, to turn a binary tree into a heap isn’t difficult either. Let’s consider, for example, how Figure 1 was transformed into Figure 2. This required just four swaps of a parent with a child, signified by the arrows in Figure 2. Start at the bottom of the tree, looking at the little three-member subtrees: in Figure 1, that’s “S” with “T” and “R”, and “I” with “E” and “E”. If any of them isn’t a heap, swap the top-level item with its largest child; this makes the subtree a heap (that’s important, so make sure you understand it). For example, the “S” is the top-level item of the little subtree made up of “S” with “T” and “R”; swap it with “T”, and now the subtree is “T” with “S” and “R”, which is a heap. When all bottom-level subtrees are heaps, move up to the next level and do it again.

The notion of “do it again” now turns out to be a little more complicated. We can see this from our example. In the previous step, the subtree in Figure 1 made up of “S” with “T” and “R” wasn’t a heap, so we fixed it by swapping “S” downwards. Now, when we move up a level, we encounter the situation shown in Figure 3, where we have to deal with the “H” at the top of this subtree. This “H” is not the top of a heap, so we swap it with the “T” below it; but things still aren’t right, because now the “H” in its new position still isn’t the top of a heap! Thus it has to be swapped into place again, exchanging it with the “S” below it. After swapping the “H” downwards twice like this, Figure 3 is transformed into a heap.

picture
Figure 3: A subtree ready to be heapified

The word for what are doing to each subtree we examine is “heapify”. We turn the subtree into a heap by swapping just the top-level item down and down, as necessary. Observe that the reason this is possible is that previously we have already seen to it that all subtrees of this tree are heaps; thus, if this tree is not a heap, the item that is out of place is just the top-level item, because this is the only item that has not yet been dealt with.

Let’s specify rigorously, then, the rule for how to heapify a tree which is a heap except for its top-level item. Swap the top-level item with its largest child, and stay with that item, continuing to swap it down the tree, changing places with its largest child, until it reaches a position where either it is larger than both its children or it has no children (because it’s reached the bottom).

We are now ready to state the algorithm for turning a whole tree into a heap. Start with the subtrees at the bottom level of the tree. If any of the subtrees at this level isn’t a heap, heapify it. When you’ve done that for every subtree at the present level, move up a level and do it again.

So far, so good. But there’s just one problem. What we really want to sort is not a binary tree at all; it’s an array (or something analogous to an array). For example, the letters of the sentence “This is a tree” do not of themselves constitute a tree; they are just eleven letters in a linear order, “thisisatree”. The solution is to devise a mapping between the items of an array and a binary tree; in effect, this mapping will allow us to treat an array as a tree.

It is very easy to describe such a mapping. The rule (which depends on the supposition that the array is 1-based) is simply this: (1) the first item of the array is the root item of the entire tree; (2) for the item at index n, its children are the items at indexes n*2 and n*2+1, and its parent is the item at index n\2 (remember that the backslash signifies integer division). If you look at Figure 1 you will see that it implicitly illustrates this rule. For example, consider the “s” in “this”, which is character 4. Its first child should, according to our rule, be character 8, which is the “t” in “tree” — and indeed it is.

In contrast to the quantity of talk necessary to describe it, Heapsort is now astoundingly easy — and brief — to implement. The notion of working our way up the tree from the bottom level is as simple as running backwards through the array. To prevent wasting cycles on items that have no children, we start at a position just past the last item’s parent.

Heapsort for an array of ComparableThings:

Sub heapsort(a() as comparableThing)
   dim i,u as integer
   u = ubound(a)
   for i = u\2+1 downto 1
      heapify(a, i, u)
   next
End Sub

The notion “heapify” was described in detail earlier, and is easiest to express recursively.

Heapify:

Sub heapify(a() as comparableThing, parentIndex as integer, lastIndex as integer)
   dim childIndex as integer
   dim temp as variant
   childIndex = parentIndex*2
   // if item has no children, do nothing
   if childIndex > lastIndex then
      return
   end
   // point at largest child
   if childIndex+1 <= lastIndex then
      if a(childIndex).shouldSwapWith(a(childIndex+1)) then
         childIndex = childIndex+1
      end
   end
   // if needs swapping, swap and continue heapifying
   if a(parentIndex).shouldSwapWith(a(childIndex)) then
      temp = a(childIndex)
      a(childIndex) = a(parentIndex)
      a(parentIndex) = temp
      heapify(a, childIndex, lastIndex)
   end
End Sub

But we are only half finished, because what we’ve created is a heap, not a sorted array. For example, if the initial array consists of the letters “thisisatree”, the resulting order is “ttssiiahree”. (You can see this in Figure 2, reading across each row in order.) We must finish by extracting the items into true sorted order.

The obvious way to do this is to take advantage of the fact that in a heap, the root item is by definition the largest item. The root item of the heap is the first item of the array. Since it is largest, this means that the first item of the array should be last. So we swap the first item of the array with the last item. The item at the end of the array is now in its proper sorted position!

Now shorten the array by one — that is, look at the whole array except for the item at the end which is properly sorted already. This shorter array is a heap, except possibly for the new first item, which is the top-level item of the tree. Well, when we have a tree that is a heap except possibly for the top-level item, we know how to make it a true heap: heapify it! So we do, and now the first item of the array is the largest item of the (shorter) array. So we swap it with the last item of the (shorter) array. Now shorten the array again and do it again, and so forth. This is easily expressed as a brief addition to our Heapsort method:

Heapsort, final version:

Sub heapsort(a() as comparableThing)
   dim i,u as integer
   dim temp as variant
   u = ubound(a)
   for i = u downto 1
      heapify(a, i, ubound(a))
   next
   for i = u downto 2
      temp = a(i)
      a(i) = a(1)
      a(1) = temp
      heapify(a, 1, i-1)
   next
End Sub

That’s it; we’ve finished. It is possible to tweak the algorithm a bit more, but our object here is instruction, not perfection. If you find it annoying that the same swapping code occurs in both the Heapsort and Heapify methods, feel free to fix this in whatever way you consider most elegant.

How good is Heapsort? It’s very good indeed, because the tree structure spreads even a large number of items into a relatively small number of levels — the number of levels rises only logarithmically in relation to the number of items — and this in turn limits the number of swaps, because every swap is between adjacent levels. For example, consider the second For-loop in Heapsort. Even in the worst case, where on every single pass through the loop the top-level item has to be swapped down through every single level, the number of swaps is only n log n, where n is the number of items. The first For-loop turns out to work much the same way; in fact, in practice it turns out that the two For-loops usually take roughly the same time. Mathematically, it can be shown that the total cost of Heapsort, taking both comparisons and swaps into account, grows no faster than 3n log n.