Lab 11: Heaps and heapsort; generic methods

Task 0: Complete lab evaluations

We will begin by taking a few minutes to complete evaluations for the lab component of the course.

• These evaluations are only for the teaching fellows/assistants. There is a separate evaluation of the undergraduate course assistants that you will complete as part of Problem Set 8, so please don’t comment about the CAs on today’s form.

• Your evaluations are anonymous, and we will not receive the results until after all final grades have been submitted.

• Comments in the text fields are valued and encouraged. Please try to answer all questions, but if a question is not applicable or you do not wish to answer it, you can simply skip it.

Here is the URL that you should use: bu.campuslabs.com/courseeval

• Enter your BU login name and Kerberos password, and complete the evaluation for your CS 112 lab section (the one with the section number that the TF/TA will write on the board). Please do not evaluate your lecture section at this time.

• When you are done with the survey, please close the separate browser tab.

Thanks in advance for taking the time to provide your feedback about the labs!

Task 1: Review heap basics

Your work for this task should be done on paper. Please show your work to a staff member before you leave the lab.

Consider the following heap:

1. Which node would be in position 4 of the corresponding array?

2. Given the node in position 4, how could you use arithmetic to determine:

   • the position of its left child (if any) in the array
   • the position of its right child (if any) in the array
   • the position of its parent in the array

3. If we call the remove() method on this heap:

   • Which item will be removed?
   • Which item will be copied into the position of the removed item and then be sifted down to restore the heap?
   • What will the tree look like after this call to remove()?

4. What will the heap look like after a second call to remove()? After a third call?

5. After completing the three calls to remove(), we then use the insert() method to add an item with a key of 21. What will the tree look like after that insertion?

Task 2: Turn an array into a heap

Your work for this task should also be done on paper.

1. Consider the following array:

   {5, 3, 12, 8, 7, 4, 6}
   

   Draw the corresponding complete tree.

2. Now turn the complete tree into a heap. Remember that you should start by sifting down the rightmost interior node in the corresponding array (or, to put in another way, the parent of the last item in the array).

Task 3: Trace heapsort

Your work for this task should also be done on paper.

Heapsort begins by turning an array into a heap, and then it uses a sequence of heap removals to sort the array.

Each heap removal removes the largest remaining item from the heap, and the removed item is then placed in the correct position in the array – beginning with the rightmost position and working backwards from right to left.

In Task 2, you already turned an array into a heap. Now trace through the remaining steps that heapsort would take to sort that array, showing the state of the array after each new element is put into place.

Task 4: Write generic methods

Our original sorting algorithms were limited to arrays of integers. To allow them to sort other types of data, we need to do two things:

• use a generic method: a method that includes a type variable in its header

• put a restriction on the type variable to specify that it can only be replaced by a type that implements the built-in Comparable<T> interface that we have discussed in lecture.

For example, the heapsort method from lecture has a header that looks like this:

public static <T extends Comparable<T>> void heapSort (T[] arr)

The restriction extends Comparable<T> means that the objects in the array are guaranteed to have a compareTo() method that we can use to compare them. To do so, we will make calls that look like this:

item1.compareTo(item2)

This call will return:

• a negative number if item1 is less than / comes before item2
• a positive number if item1 is greater than / comes after item2
• 0 if item1 is equal to item2.

In Lab11Task4.java, we’ve included the versions of insertion sort and quicksort that we examined earlier in the semester. We’ve also included the helper methods used by quicksort.

Modify these methods so that they can be used to sort arrays of any type that implements Comparable<T>. This will require the following steps:

1. Modify the header of insertionSort() to make it generic. Don’t forget to include a type restriction, just as we did for heapSort().

2. Revise the body of insertionSort(). In particular:

   • Find any local variables that are used to hold array elements, and change their types to be T.

   • Find any comparisons of array elements, and change them to use an appropriate call to the compareTo() method.

3. Compile your revised code, and debug it as needed. Once it compiles, test it from the Interactions Pane:

   > String[] greeting = {"hello", "how", "are", "you", "today"};
   > greeting
   { hello, how, are, you, today }
   > Lab11Task4.insertionSort(greeting);
   > greeting
   { are, hello, how, today, you }
   

4. Modify the headers of quickSort() and its helper methods. Most of the helper methods will need to be generic with a type restriction, but the swap method’s header can be revised more simply as followed:

   public static void swap(Object[] arr, int a, int b)
   

   This method does not need to be generic because swap doesn’t compare objects itself and it doesn’t call another method that does so. Therefore, using an array of type Object is sufficient.

5. Revise the bodies of the helper methods as you did in step 2. However, swap()‘s local variable should be of type Object rather than T.

6. Compile your revised code, debug it, and test it:

   > String[] languages = {"java", "python", "haskell", "c"};
   > Lab11Task4.quickSort(languages);
   > languages
   { c, haskell, java, python }
   

Task 5: Submit your work

You should show the paper with your work to the teaching assistant.

You should use Apollo to submit your modified Lab11Task4.java file.

Don’t worry if you didn’t finish all of the tasks. You should just submit whatever work you were able to complete during lab.

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate lab section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.