A 3D View of Heapsort

Heapsort works in two phases. First, it arranges the elements being sorted into a heap, a complete binary tree in which the value of each node is larger than the values of each of its children. Second, it repeatedly removes the root (i.e., the largest value among the elements) from the heap, sets it aside, and reestablishes the heap property, doing so until the heap is empty.

Heaps can be implemented as arrays by placing the root node at position 1, and for each node at position i, placing its left child at position 2i, and its right child at position 2i+1.

The 3D views below expose both of these properties. When viewed from the front, as in the upper-left figure, we see the heap configured as a traditional tree (drawn in the xy plane). Each node in the tree is an element of the array being sorted, and has depth (in the z dimension) proportional to its value. Thus, nodes at the top of the tree are longer (or deeper) than those near the leaves. When the tree is viewed from the side, as in the upper-right figure, we see a classical sticks view of sorting algorithms (see also 3D view of elementary sorting algorithms). The lower-left figure shows the same structure from an oblique viewing angle. Notice the relationship between the two representations. The lower-right figure shows the algorithm when it's almost completed.

The value of elements are also encoded by colors along the spectrum: large elements are displayed in red and small elements in blue. Color is not crucial in the sticks representation, because the value of a stick is encoded by its length, but it is quite helpful in the tree view.

Of course, it is possible to show the two perspectives - the tree and the array - as separate views, each in its own window, without using 3D graphics. However, the viewer must mentally integrate the different views in order to understand them as a whole. The 3D view alleviates this problem.

Here are a smaller and a larger MPEG movie showing the animation in progress.


This animation is described in SRC Research Report 110a, and in an accompanying video tape, SRC Research Report 110b.


Zeus Home Page / Systems Research Center / Compaq Computer Corporation

Legal Statement Privacy Statement