Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 4 and 5 Hints for Heapsort

Due Friday, March 3, and Friday, March 10, 2000.

Heapsort is actually a clever implementation of selection sort. The difference between heapsort and simple selection sort is that heapsort uses a heap to store the items that have not yet been selected.
A heap is a data structure that permits the operations insert and deletemin. Of course, any unsorted array is a heap by that definition, but it takes linear time to execute deletemin.
Rather, we implement a heap as an almost complete binary tree which we can store in an array. The rule is that the root is stored in position 0, and the parent of the item in position i is the items in position (i-1)/2, using truncated division.
The best way to run heapsort is to define the heap backwards, that is, set it up so that you execute deletemax. The heap condition is that any item is less than or equal to its parent, making the root the maximum.
Linked Binary Tree Implementation. Details later ...