Article Preview
Buy Now
COLUMN
Sorting, Part 2
Heaps of Fun
Issue: 1.3 (December/January 2002)
Author: Matt Neuburg
Author Bio: Matt Neuburg is the author of REALbasic: The Definitive Guide, and a member of the editorial board of REALbasic developer.
Article Description: No description available.
Article Length (in bytes): 11,511
Starting Page Number: 34
Article Number: 1317
Resource File(s):
1317.zip Updated: 2013-03-11 19:07:56
Related Link(s): None
Excerpt of article text...
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
REALbasic: The Definitive Guide .)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.
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.
...End of Excerpt. Please purchase the magazine to read the full article.