Getting started
Priority Queue: Heap and Heapsort
Stress Tests - Timing Tests
Version: 5.2.1

Lab 10

Stress Tests; HeapSort, Priority Queue

Goals: One goal of this lab is to learn how to implement the heapsort algorithm as well as the priority queue implemented as a heap. This is just a practice in understanding how one can convert a description of an algorithm into working code.

The second, more important goal of this lab is to illustrate on concrete examples and experiences the differences in the algorithm complexity.

Homework assignment for this week is to finish anything you did not finish during the lab and turn in your results.

Getting started

Create a project with the name HW10Problem1. Download the following files:




Unzip and import the whole folder you get (named student) into your project. (Alternately, define a new Package named student, highlight it, and import the files in the student folder into it.

Add sorting.jar, jpt.jar. and tester.jar to the classpath for your project. Finally, save the file citydb.txt in the same directory in your EclipseWorkspace where the src and bin files are stored for this project.

Your project should be ready to run, but we will wait with that.

Note: The files in the file are saved in a folder named student. You have to import the whole folder into Eclipse. It will show up as a new package in your project.

Notice that both files in this package start with the declaration package student;. This is the way Java programming language allows you to combine together classes that belong together and form a comprehensive collection that can then be turned into a library.

Run the project using the TimerTests class as the class that contains main, to make sure you have all pieces in place. When the File Chooser Dialog comes up select the file citydb.txt.

Priority Queue: Heap and Heapsort

Our first goal in this section is to design a priority queue using the heap algorithm. We then use this to implement the heapsort algorithm and add it to a collection of algorithms to be evaluated.

Note: If this part is taking too much time, put it aside and make sure you start the second half of the lab during the lab time, so that you know how to run the stress tests.

Recall the properties of the Heap from today’s lecture:

If it helps you, draw the picture of the tree and manipulate stickies or pieces of paper to see how the algorithms for inserting and deleting nodes work.

Typically, we represent this heap as an ArrayList<T> with the first item (at index 0) unused (maybe null).

StressTests - Timing Tests

Your job is now to be an algorithm detective. The program we give you allows you to run any of the six different sorting algorithms on data sets of five different sizes using three different Comparators to define the ordering of the data. When you run the program, the time that each of these algorithms took to complete the task is shown in the console.

Question: How many timing results would you collect if all of these tests rans successfully?

Set up a new Run Configuration where you select the class sorting.Interactions as the main class. Run the program. It will come up with a GUI with several buttons. You need to use them in the correct order:


Spend about fifteen minutes trying to answer some of the following questions. Finish the work as a part of the Assignment 10.

Run the program a few times with small data sizes, to get familiar with what it can do. Then run experiments and try to answer the following questions: