Due Date: midnight Wednesday, December 4

Background

Lab 10 is designed to give you experience in implementing a general comparable heap. The data structure that you use to store the heap must be an array or array-like class such as ArrayList. Since a heap is tree with a few more constraints, this lab will also give you experience in using an alternate data structure to represent a tree.

So now the cheesy story for the lab. Recently midterm grades were given out for the Introduction to Programming classes, Mark must now meet with the students to discuss their grades and advise them on the best course of action in light of the the recent grades. Mark is swamped with work, so he has given you a list of all of the students and their grades so that you can sort them. Students that do poorly need to meet with Mark sooner than those that are doing well; if the students have the same grade then they must be ordered alphabetically according to their andrew id.

What You'll Need

The lab10 zip file is provided for you. It contains the class files for the solution, test files, and the source templates that you will be required to fill in.

Assignment

As you have learned in lecture, heaps are trees with the following additional constraints: heaps are complete and heaps maintain the heap order property. The heap order property states that the parent of a node will be less than its children if the heap is a min-heap, and the parent will be greater than its children if the heap is a max-heap. Insertion and deletion operations in a heap are O(log n) where n is the number of elements in your heap. Also, since the top element of the heap is the always going to be the smallest or largest element (depending on the type of heap), you can use a heap to sort its data by removing the top element until there are none left. The data in the sequence of removals will then be in increasing (decreasing) order. The running time of this sort, if you have n elements in the heap, will be O(n log n) since you will be performing n deletes which makes the cost to sort the heap n*[cost of one delete]. Since the cost of one delete is O(log n), the total cost is O(n log n).

For this assignment you will have to make a min-heap of students. A student has an andrew id, first name, last name, and mid-term grade.

The Student class is provided but it is incomplete - the compareTo method is not written. As indicated above, you must first compare the grade of each student, and if the grades are equal then compare andrew id's and sort the students in increasing order by their andrew id. Since andrew id's are unique you will not have to sort by the first and last name fields.

As the main objective of the lab is to have to learn about heaps, it would not be a bad guess that you will have implement one. The heap you are to implement is a min-heap of Comparables. We provide you with a basic outline of the class in ArrayHeap.java. It is your responsibility to fill in the method stubs. Since Student implements the Comparable interface, you will be able to use this class for sorting your students. The following is the list of method stubs in ArrayHeap.java:

• ArrayHeap(Comparable[] values) - takes the element in the array values and inserts them into the heap
• ArrayHeap() - creates an empty ArrayHeap
• void insert(Comparable c) - inserts a Comparable object into the heap, preserving the heap order property.
• Comparable deleteMin() - removes and returns the minimum element from the heap, preserving the heap order property.
• Comparable findMin() - returns the minimum element from the heap without removing it
• int numElements() - returns the number of elements in the heap.
• String toString() - returns the String containing all the elements in level order

In addition to the methods above, you must also print out your array in sorted order. You may create a method to do this or you may add the code to the main function of ArrayHeap. It is up to you.

When you are implementing the above methods consider the situation of inserting into a full array. If you try to insert outside the bounds of the array you will get an IndexOutOfBounds exception. Since ArrayLists resize themselves dynamically, you may want to use them instead of arrays, however you do have a trade off in that you will have to do a lot of casting. If you choose to use arrays, you will have to manually resize your array if it is full. Everything else you need to know about heaps, at least for this assignment, should have been covered in class and recitation, however if you need quick refresher, visit this heap site.

When you run ArrayHeap be aware that it takes in a command line argument. So you would run it in the following manner for test1.txt.

java ArrayHeap test1.txt

Handing in your Solution

Use the Intro Programming dropoff form to submit your zip file.