Lab10 Heaps

CSC220 Lab10
Heaps
The goal of this week’s assignment is:
1. Practice using heaps
2. Learn about the importance of debugging
Part 0
• Create a new Java project and call it Lab10.
• Create a package inside your project and call it lab10.
• Download the Lab10-Assignment10 ZIP folder from Blackboard and copy in
the following files:
• MaxHeap.java. You will be working on developing methods for this class.
This class represents a max heap. This class has been partially
implemented for you.
• HeapTester.java. A set of test cases your code should handle.
Part 1 – Problem description
For this lab, you are asked to write methods to complete the implementation of a binary
max heap class. In a binary max heap, each node can have at most two children, and
the data in the parent node must be greater than or equal to all of its descendants.
Remember that, like min heaps, there is no relationship between the data values of the
siblings of a specific parent (i.e., the right child does not have to be greater or
smaller than the left child). The max heap in this case is nothing but an array. Recall
from the lectures, for implementing a binary tree (or in this case a heap) using an array,
we need the following rule: for any node at index i, its two children are at index (i*2)+1
and (i*2)+2. The functions to access the parent, left child or right child of a node have
been implemented for you.
Given an array of N values, a heap containing those values can be built, in-place, by
simply “sifting” each internal node down to its proper location. You have seen the
opposite behavior during the lecture for a min heap. For example, imagine that we
want to add 84 to the following heap that is represented using the following array:
In order to offer 84 in this max heap, we start by putting the value 84 at the last
internal node possible. Which one is it?!
Now, we need to make sure whether it is in its current position, meaning if the value of
its parent is smaller than 84, we need to swap the current node (84) with its parent till
the max heap property is satisfied. Before you continue, take a moment and think
about how the array (representing the max heap) should look like after this offer. Here
is how it should look like after the offer:
You need to convince yourself why the internal nodes have been moved around
before you continue.
Similar to lab 9, We provided a simple variation of in-order traversal of a tree
(suggested in the book – Chapter 17.2 – page 1031): “instead of printing values all on
a line, we will print them one per line and use indentation to indicate the level of the
tree”. For example, the previous heap can be printed using a call to printSideways():
0
0
0
5
0
0
0
84
0
10
0
17
0
3
0
The extra zero values are due to the fact that the max heap has been initialized so
that it can contain 15 elements. You need to imagine rotating this output 90 degrees
in a clockwise fashion (or tilting your head to the left) to see the tree structure. This
function can come handy. There is also a toString() method that you can use to
return a String representation of the heap.
Before you move on to the next part, take a couple of minutes and look at the definition
of the methods provided for you and the fields of this class. Consult the lab TAs if you
have questions!
Remember: you are NOT allowed to change the signature of the methods. However,
you are more than welcome to create and use helper methods.
Finally, please note that you do not need to worry about the array containing the heap
running out of space (keep this in mind, when you are testing your code – not to add
more than the array can contain).
This week you are required to implement the following methods. We will only do the
first three during the lab:
1. public MaxHeap(int maxsize)
2. public void offer(int element)
3. public int poll()
4. public void sort()
5. public MaxHeap(int[] arr)
Part 2 – MaxHeap constructor
By the end of this week’s assignment you are going to implement two constructors for
this class. We start with the easy constructor for the lab. The signature of this
constructor MUST be the following (only modify where it says “FILL IN” – DO NOT
change the signature):
public MaxHeap(int maxsize)
As the signature of this method suggests, this is a constructor for this class. This
method will initialize the status of the member variables (i.e., size) of this class based
on the input parameter. So, this function will create the array (heap) with the specified
size and initialize all of its elements to be zero. You need to be careful about whether
any other field needs to be initialized at this stage (hint: think about what the value of
size should be).
Part 3 – offer method
The signature of this method should be (only modify where it says “FILL IN” – DO
NOT change the signature):
public void offer(int element)
This function will offer the given value (element) into the heap and position it into the
correct location. Go back to the problem description part and make sure you are
following the steps given EXACTLY. The element is supposed to be added to the latest
position available in the heap array and then you must make proper changes to the
heap structure to maintain the max heap property. Don’t forget to update the size value.
Part 4 – poll method
The signature of this method should be:
public int poll()
This function will remove and return the maximum value stored in the max heap.
Recall that, by definition, this value would be stored in the root. The logic here is
similar to removing min from the min heap covered during the class. To implement
this function, start by swapping the root with the last leaf, sift the new root down to
restore heap property. If the heap is empty this method should return -1.
Part 5 – Test your code
As usual you need to test the functionality of the methods you have implemented. A set
of test cases has been provided for you in HeapTester.java. Uncomment the lab
portion of the tests and run the main function. If you see any red text that says “TEST
FAILED”, you need to debug your code.
How to debug your code?
1. Use the Eclipse debugger you learned about during the first lab 2. If you see
JavaStackOverflow, that means that you have an infinite recursive call and your
recursive call is filling up the “call stack” (we talked about this concept in class). Go
back and debug the method that is causing the problem. 3. Infinite loops! How
would you know you have an infinite loop? As you should know from CSC120, if
you have an infinite loop in your code, your code will not stop running. An easy way
to inspect that in Eclipse is to look at your console window, if your code is done
running the console should look like the following:
If the little square marked above is red and continues to stay red, that means
your code has an infinite loop!
Don’t forget: lab/assignment is due Thursday night @ 11:59pm!