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/2011S/labs/code/heapsort/HeapSort.java .

Exercises

Exercise 1

     /**
      * 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[0].

Exercise 3

If the answers are not correct, I suggest you use a smaller heap (i.e., 2⁽³⁺¹⁾-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