HeapOfTrouble

Background:

This lab 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 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, Semester grades were given out for the Advanced Placement Computer Science class, George must now meet with the students to discuss their grades and advise them on the best course of action in light of their recent grades. George 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 George sooner than those that are doing well; if the students have the same grade then they must be ordered according to their Lynbrook id.

Assignment:

As you have learned, 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 in case of a max-heap) 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 a Lynbrook id, first name, last name, and semester 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 Lynbrook id's and sort the students in increasing order by their Lynbrook id. Since Lynbrook 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 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 HeapPriorityQueue.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 HeapPriorityQueue.java:

• HeapPriorityQueue() - creates an empty HeapPriorityQueue
• void add( Object item ) - inserts a Comparable object into the heap, preserving the heap order property.
• Object remove() - returns and removes the next element from the heap according to its given priority, preserving the heap order property. The priority is determined by the compareTo() method. Therefore all elements added to the priority queue must implement the Comparable() interface. The elements will be returned according to their natural ordering as determined by compareTo().
• Object peek() - returns the next element from the heap without removing it
• boolean isEmpty() - returns true if the priority queue has no elements, false otherwise.
• String toString() - returns the String containing all the elements in level order

In addition to the methods above, you must also print out grades in sorted order. The method you must complete is located in the main driver program (HeapOfTrouble.java)..

Everything you need to know about heaps, at least for this assignment, should have been covered in class and the class notes, however if you need quick refresher, visit this heap site.

Instructions:

1. Submit your source code for the entire program and the run output described above.