Lab 13

Lab Partners

Everyone should work with one lab partner on this assignment.

Purpose

The purpose of this in-lab is to help you better understand heap sort.

Preliminaries

Create a BlueJ project named inlab13 and place the following code into it:

• Lab13.java
• HeapSort.java

Part I: Diagrams (3 points)

Consider the following initial elements in the following order in an array: 5 6 4 3 7 8 2 1 9 0.

• Draw a picture of the heap after each element is inserted by the buildHeap method. There should be 10 pictures in all.
• Draw a picture of the array that corresponds to the final heap that you found in the step above.
• Draw a picture of the entire array after each element is removed by the sortHeap method. There should be 9 pictures in all.

Part II: Coding Task (4 points)

Modify the HeapSort class so that the findKthLargestItem task works correctly. Test your method with the following inputs:

• 10 (the size of the array) and 1 (the largest element)
• 10 and 2
• 10 and 5
• 10 and 6
• 10 and 10

When your code is working, call over Mike or a consultant. This person will test your program and report the results to Mike.

Part III: Efficient Code (3 points)

After Part II is finished, modify the HeapSort class so that it does the minimal amount of work to find the kth largest item.

When your code is working, call over Mike or a consultant. This person will test your program and report the results to Mike.

What to Submit

• Submit your Part I hand-drawn pictures to Mike.

Before Lab Ends

Delete any BlueJ projects that you created and empty the recycle bin. Thanks.