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, write a simple main method to test the following:

   > String[] greeting = {"hello", "how", "are", "you", "today"};
   > System.out.println( greeting );
   { hello, how, are, you, today }
   > Lab11Task4.insertionSort(greeting);
   > System.out.println( 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);
   > System.out.println( languages );
   { c, haskell, java, python }
   

Task 5: Submit your work

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