Introducing the “Welcome to Xojo” Bundle!

New to Xojo and looking for guidance? We've put together a terrific bundle to welcome you! Xojo Bundle

This bundle includes six back issues of the magazine -- all of year 21 in printed book and digital formats -- plus a one-year subscription (beginning with 22.1) so you'll be learning all about Xojo for the next year. It's the perfect way to get started programming with Xojo. And you save as much as $35 over the non-bundle price!

This offer is only available for a limited time as supplies are limited, so hurry today and order this special bundle before the offer goes away!

Article Preview

Buy Now

Issue 1.3


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):

Download Icon 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.