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.
-
Store the items in the array arbitrarily. The first step is to reorganize
the array so that the heap condition holds. This step takes O(n)
time if done efficiently.
-
After i iterations of the main loop, the heap will be held in
the first n-i positions of the array, while the last i
positions of the array will have their final items. When i=n,
we are done.
-
One iteration of the main loop consists of the following steps, provided
i < n :
-
Exchange the maximum item in position 0 with the item in position
n-i-1, that is, the last item in the heap. Now, decrement
the heap. This means that that item we just moved is in its final
position.
-
Demote the item in position 0 as many times as needed in order to
restore the heap property.
If i=n do nothing, as there is only one item in the heap.
Linked Binary Tree Implementation.
Details later ...
