Laboratory: Heap Sort
 CSC 207 Algorithms and Object Oriented Design Spring 2010

Summary: In this lab, you will implement part of a max heap to percolate down for a heap sort.

# Preparation

1. Create a directory for this lab:
`  mkdir somewhere/heapsort`
2. Go to your new directory:
`  cd somewhere/heapsort`
3. Copy the file for this lab:
`  cp ~weinman/public_html/courses/CSC207/2010S/labs/code/heapsort/HeapSort.java .`

# Exercises

## Exercise 1

The following code is taken from Figure 21.14 in Weiss.
``````
/**
* Internal method to percolate down in the heap.
* @param hole the index at which the percolate begins.
*/
private void percolateDown( int hole )
{
int child;
AnyType tmp = array[ hole ];

for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize &&
compare( array[ child + 1 ], array[ child ] ) < 0 )
child++;
if( compare( array[ child ], tmp ) < 0 )
array[ hole ] = array[ child ];
else
break;
}
array[ hole ] = tmp;
}``````

Recall that the given min heap uses a sentinel at array location zero. This impacts where the children are, as well as how the size of the heap relates to the index of the last node.

In the next exercise, you will be modifying this method to use a zero-based heap, rather than the one-based heap this method is written for. Thus, you are strongly encouraged to record your answers to the following questions on paper, so as to help you develop your solution.

1. What is the effect and purpose of the statements assigning `tmp` to `array[ hole ]` and vice-versa?
2. What is the meaning of the following for-loop test? That is, what is it expressing?
``hole * 2 <= currentSize``
3. What is the meaning and purpose of the for-loop "increment" `hole = child`?
4. What does the assignment to `child` accomplish? What child is this? (No singing Greensleeves, now.) Left or right?
5. What does it mean if `child == currentSize`?
6. How would you express this same meaning in a zero-based heap?
7. What is the effect of the `child++`? (That is, what is the meaning, not "the integer `child` is increased by one").
8. Why does the `compare` statement indicate the increment is reasonable and appropriate?
9. What does the following assignment do?
``array[ hole ] = array[ child ];``
Why shouldn't we be worried about overwriting the array entry at `hole`?
10. Why does the `compare` statement indicate this is the appropriate action?
11. Why do we `break` out of the loop otherwise?

## Exercise 2

1. Open `HeapSort.java` in Emacs.
2. This file contains several methods. Most notably, `heapsort`, the implementation of a standard heapsort given in Weiss Figure 21.28. Review that now and be sure you understand how it works.
3. Inspect the signature and documentation of the `percDown` method to be sure you understand how it is supposed to work.
4. Using your answers from exercise 1, and the original implementation of `percolateDown` as a model, implement this version of percolate down, taking note of the following two important differences:
• This version uses a max heap, and
• there is no sentinel at zero, so the first datum appears at `array`.

## Exercise 3

Test your implementation using the `main` method in `HeapSort.java`. If the answers are not correct, I suggest you use a smaller heap (i.e., 2(3+1)-1=7 nodes), and add print statements that tell you where the hole is, what is being swapped for what, and what indices the swap is between. In addition, you may wish to carefully review your answers to the questions in Exercise 1, and make sure the logic (in addition to the arithmetic) still holds for your implementation in Exercise 2.

# For Those with Extra Time

## Exercise 4

Write and test a recursive version of `percDown`.
Created: Jerod Weinman, 6 May 2009