CSC 207  Grinnell College  Spring, 2012 
Algorithms and ObjectOriented Design  
This lab provides practice with several basic algorithms related to heaps, as implemented with arrays.
A heap is a binary tree with the property that the value at each node is larger (according to some ordering) than the values stored in either child. Further, we restrict our attention to trees which are completely balanced. All nodes have 2 children, except at the bottom of the tree. The last row of the tree may not be full, but any items on the last level are moved left as much as possible. For example, the following tree illustrates the shape of a tree and the ordering of values within the tree.
To identify the nodes in a tree, the simplest approach is to number the nodes levelbylevel from the root downward. Within a level, nodes are numbered left to right.
In examining the label nodes, a pattern emerges: for each node labeled i, the left child has label 2*i and the right node has label 2*i+1.
If we start labeling at 0 rather than 1, the labeling of nodes becomes:
In the context of 0based labeling, identify a pattern for moving from a node with label j to its left child and its right child. What labels would be found on the left and right nodes of a node with label j?
Since nodes in a heap fit a straight forward identification system, there is a natural mapping between the logical nodes in a heap and the indexed elements of an array.
In class we considered how to insert an item into a heap and maintain the structure. In each case, we first place the item at the end of a tree (as far left as possible in the last row). The item then is worked up from its position, until the data in the tree are appropriately ordered.
The following heap repeats the structure given at the beginning of this lab:
Using this structure as a start, insert the values 30, 25, 55, 81, and 95. Show the structure of the tree and the values in each node after each insertion.
In class, we also considered how to remove the toppriority item from a heap: remove the root as the item to be returned, move the last item from the end of the heap to the root, and work that item down in the heap until the data are properly ordered.
In class, we discussed starting with an array of data and working from the bottom toward the top to rearrange the data to yield a heap.
Suppose an array a[12] is initialized with a[i] = 20i for each i. What rearrangements, if any, need to be done in order to make the corresponding tree structure into a heap? Show the data in the array once a heap is achieved.
Suppose an array a[12] is initialized with a[i] = i for each i. What rearrangements, if any, need to be done in order to make the corresponding tree structure into a heap? Show the data in the array once a heap is achieved.
The following parts of this lab are lightly edited from a "Heap Sort" lab, written by Jerod Weinmen.
Steps 6—9 of this lab refer to a partiallywritten HeapSort class.
Import this class into a heapsort package within eclipse.
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 exercises, you will be modifying this method to use a zerobased heap, rather than the onebased heap this method is written for.
Record your answers to the following questions on paper, so as to help you develop your solution.
tmp
to array[ hole ]
and
viceversa?
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 ];Why shouldn't we be worried about overwriting the array entry at
hole
?
compare
statement indicate this is the
appropriate action?
break
out of the loop otherwise?
Complete the HeapSort class:
HeapSort.java
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.
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]
.
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.
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/207.sp13/labs/labheaps.shtml
created 7 May 2012 by Henry M. Walker revised 7 May 2012 by Henry M. Walker expanded with code 11 January 2013 by Henry M. Walker 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 