CSC 207 | Algorithms and Object Oriented Design | Spring 2011 |
Summary: In this lab, you will implement part of a max heap to percolate down for a heap sort.
mkdir somewhere/heapsort
cd somewhere/heapsort
cp ~weinman/public_html/courses/CSC207/2011S/labs/code/heapsort/HeapSort.java .
/**
* 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.
tmp
to array[ hole ]
and
vice-versa?
hole * 2 <= currentSize
hole = child
?
child
accomplish? What
child is this? (No singing Greensleeves, now.) Left or right?
child == currentSize
?
child++
? (That is, what is
the meaning, not "the integer child
is
increased by one").
compare
statement indicate the increment
is reasonable and appropriate?
array[ hole ] = array[ child ];
hole
?
compare
statement indicate this is the
appropriate action?
break
out of the loop otherwise?
HeapSort.java
in Emacs.
heapsort
, the implementation of a standard
heapsort given in Weiss Figure 21.28. Review that now and be sure
you understand how it works.
percDown
method to be sure you understand
how it is supposed to work.
percolateDown
as a model, implement
this version of percolate down, taking note of the following two
important differences:
array[0]
.
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.
percDown
.