15-121 SPRING 2010 [CORTINA]

LAB 9

Marjory the Trash Heap from Fraggle Rock

In this lab, you will implement a minheap using an array to complete an application to sort a collection of integers.

EXERCISES

Download the project Lab9.zip. The project contains two classes. One class is an application called HeapSort that creates a minheap, inserts a set of integers into the minheap, and then removes the minimum from the minheap repeatedly to build a sorted array. The other class will contain the code for the minheap. Read the comments in the MinHeap class so you understand what each field stores.

Complete the method insert in the MinHeap class that inserts a value into the minheap. Remember that when you insert into a heap, you add the element into the next available position in the tree in the last level (or start a new level if the last level is full), and then fix the tree so it satisfies the minheap property. Your implementation for this lab should use iteration, not recursion. Run the heapsort application which shows the contents of the minheap after each insert is performed. (Ignore the output for the remove operations since you did not do these yet.) On a sheet of paper, draw each heap that is printed after a value is inserted to make sure you are coming up with the correct heap after each insert.
Complete the method remove in the MinHeap class that removes the minimum from the minheap. Remember that when you remove the minimum from the heap, you move the last element in the last level to the root, and then fix the tree so it satisfies the minheap property. Remember that your method must return the minimum value that was in the root. Your implementation for this lab should use iteration, not recursion. Run the heapsort application and look at the contents of the minheap after each remove is performed. On a sheet of paper, draw each heap that is printed after a value is removed to make sure you are coming up with the correct heap after each remove.

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of lab, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER

Modify the heap so that it contains Comparable elements of type E.
Modify the heap so that it reallocates the array to a larger size if the array becomes full and reallocates the array to a smaller size if more than half of the array is not used.
Create a simulation of an emergency room, where a patient arrives with a priority number between 1 and 99 that indicates the severity of the patient's injury (higher number = higher severity). Instead of putting patients on a FIFO queue, put them in a priority queue implemented as a maxheap. Determine the average waiting time for a patient under various arrival rates and operating times.