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*.

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:

A

*heap*is a complete binary tree. It means that every level is filled, except for the last level. The last level is filled from the left.So a heap with five nodes will have the following shape:

node-1 / \ node-2 node-3 / \ node-4 node-5

The nodes are labeled by levels from left to right, starting at 1.

The

*value*in each node is greater-than or equal-to (for some comparison definition) the values in both of its children. So the item with the highest value (highest priority) is at the root of the tree.The label of the parent of node

`i`is`i/2`The label of the left-child of node

`i`is`2*i`The label of the right-child of node

`i`is`2*i+1`

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`).

Add a

`HeapExamples`class to your project.Make three examples of the following

To build the following*heap*s by defining an`ArrayList<Integer>`for each case in your examples class and an`initHeaps`method to add the values in the appropriate order.*heap*node-1 / 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 this.myheap.add(70); this.myheap.add(60); this.myheap.add(40); this.myheap.add(35); this.myheap.add(50); }

Here are the three heaps to define:

node-1 / 80 \ / \ node-2 node-3 / 50 \ / 40 / \ / node-4 node-5 node-6 45 20 30

node-1 / 50 \ / \ node-2 node-3 / 45 \ 40 / \ node-4 node-5 30 20

node-1 / 70 \ / \ node-2 node-3 / 45 \ / 50 / \ / node-4 node-5 node-6 30 20 40

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.Design the method

`isLeaf`that consumes a node label (an`int`) and returns`true`if the node has no children (remember the numberings...).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.Design the method

`insert`that inserts a new node into the*heap*.Here is what we went over in lecture yesterday:

- Insert the new item at the next position in the bottom level (the end of the list representation). Say, this is position k.
Upheap from k:

While (k > 1 and heap(k) > heap(k/2)) { ~~~~~~swap heap(k) and heap(k/2) ~~~~~~set k to k/2 }

Design the method

`remove`that removes the node with the highest priority from the*heap*.Here is what we went over in lecture yesterday:

- save the
*root*item as a temporary - move the
*last*item into the root position - Downheap from k = 1:
While (k is not a leaf) { ~~~~~~find ck the node with the larger child of the node k ~~~~~~if heap(k) < heap(ck) { ~~~~~~~~~~~~swap heap(k) and heap(ck) ~~~~~~~~~~~~set k to ck } ~~~~~~else stop }

- save the

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 `Comparator`s
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.

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:Start with

*File Input*button. It opens the*File Chooser Dialog*and when you select the file**citydb.txt**it reads in the data for the 29470 cities.Next hit the

*TimerInput*button. It lets you select which algorithms to test, which*Comparator*s to use, and what size data should be used in the tests.Start with just a few small tests, to see how the program behaves, before you decide to run all tests.

The last choice is

*heapsort*that you have designed. The two files in the`student`package originally provided only hooks to the stress test program --- the method`heapsort`in the class`Heapsort`, so you could run the stress tests even if you did not implement the*heapsort*algorithm. The original*stub*just returned the original unsorted`ArrayList`. So,**if you are having difficulties with finishing the implementation of the**, leave it for now, and run the program with the original files in the*heapsort*`student`package.In the third step, (once you read in the data and have chosen which algorithms to run, for which data set sizes, and with which

`Comparator`s), you can run the actual timing tests by hitting the*RunTests*button.

You can repeat the last two steps as many times as you want to.

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:

Which algorithms run mostly in quadratic time, i.e.

`O(n^2)`?Which algorithms run mostly in

`O(n.log_n)`time?Which algorithms use the functional style, using

`Cons`lists?Which algorithm is the

*selection sort*?Why is there a difference when the algorithms use a different

`Comparator`?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.Produce a report with a paragraph that explains what you learned, using the

*Excel*charts to illustrate this.