CS 2510 Spring 2012: Lab12 - Stress Tests; HeapSort, Priority Queue

copyright 2012 Felleisen, Proulx, et. al.


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.

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

Unzip student.zip and import the whole folder you get (named student) into your project. Add sorting.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 student.zip 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 starts 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 yesterday'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).

  1. Add a HeapExamples class to your project.

  2. Make three examples of the following heaps by defining an ArrayList<Integer> for each case in your examples class and an initHeaps method to add the values in the appropriate order.

    To build the following heap
                    /  70  \
                   /        \
                node-2     node-3
               /  60  \      40
              /        \
           node 4     node 5
             35         50

    we would proceed as follows:

    ArrayList<T> myheap = new ArrayList<T>();
    void initHeap(){
      this.myheap.add(null); // the unused first item

    Here are the three heaps to define:

                   /   80   \
                  /          \
              node-2         node-3
             / 50 \         / 40
            /      \       /
         node-4   node-5  node-6
           45       20      30
                     /  50  \
                    /        \
                node-2      node-3
              /   45  \       40
             /         \        
          node-4      node-5   
            30          20       
                    /   70  \
                   /         \
               node-2         node-3
               / 45 \         / 50
              /      \       /
          node-4  node-5   node-6
            30      20      40
  3. Define the class PriorityQueue<T> that will represent a heap-based priority queue. It has two fields: an ArrayList<T> and a Comparator<T> that determines the ordering of priorities.

  4. Design the method isLeaf that consumes a node label (an int) and returns true if the node has no children (remember the numberings...).

  5. Design the method higherPriorityChild that consumes the index of a node that is not a leaf and produces the index of its child with the highest priority.

    Note: If the node has only one child, then this will be the one with the higher priority, of course.

  6. Design the method insert that inserts a new node into the heap.

    Here is what we went over in lecture yesterday:

  7. Design the method remove that removes the node with the highest priority from the heap.

    Here is what we went over in lecture yesterday:

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.

  1. 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 12.

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:

  1. Which algorithms run mostly in quadratic time, i.e. O(n^2)?

  2. Which algorithms run mostly in O(n.log_n) time?

  3. Which algorithms use the functional style, using Cons lists?

  4. Which algorithm is the selection sort?

  5. Why is there a difference when the algorithms use a different Comparator?

  6. Copy the results into a spreadsheet. You may save the result portion in a text editor with a .csv suffix and open it in Excel (or some other spreadsheet of your choice). You can now study the data and represent the results as charts. Do so for at least three algorithms, where there is one of each --- a quadratic algorithm and a linear-logarithmic algorithm.

  7. Produce a report with a paragraph that explains what you learned, using the Excel charts to illustrate this.

Last modified: Thu Apr 5 13:30:03 EDT 2012