COMP 212
Programming Assignment 2
Due April 10, 2000

In class we considered a number of implementations of a priority queue. Which one is the best depends somewhat on the situation. The purpose of this exercise to experiment with sorting a set of random integers using different implementations of a priority queue in order to decide which implementation is best for this problem.

To this end your first task is to implement four versions of a priority queue:

1.

PQ1 - using an unordered array.

2.

PQ2 - using an ordered array.

3.

PQ3 - using a binary heap.

4.

PQ4 - using a ternary (degree 3) heap.

For each version you should supply methods for (i) initializing an empty priority queue (ii) testing if a priority queue is empty (iii) inserting an item into the priority queue and (iv) deleting the maximum item from the queue.

Having implemented (and hopefully tested they are correct!) the above versions you are to compare how well they perform on the sorting problem. In particular, for each of the four PQs and for N = 2ⁱ, i = 0, 1, ... , 7, compute how long it takes to sort N randomly generated integers by first inserting them one at at time into the PQ, and then extracting them in order from largest to smallest using the getmax operation.

You should include in your source a commented section containing a table of your results. Also comment on how the results meet with your expectations considering the analysis performed in class.

Some Notes:

• To generate random integers use the random number generator rand() which is found in stdlib.h (i.e., you must have #include <stdlib.h> at the top of your testing program). If you want to change the seed of the number generator you can use the function srand(unsigned int).

• To time your sorts you can use the function clock() in time.h. To use it, set start_time = clock() just before you start the sort and end_time = clock() just after you finish. Then the time in seconds used by your sort is (end_time - start_time)/CLOCKS_PER_SEC (where CLOCKS_PER_SEC is a system defined constant that relates the time measured by the clock function and time measured in seconds). Don't forget to include time.h.

• The code for PQ1 and PQ3 can be found in the book (Programs 9.2 and 9.5, respectively). Note that the book uses the template command so as to allow the items in the queue to come from any class. To declare a priority queue pq of size 10 of type int use PQ <int> pq(10). To complete the book's implementations you have to write the (private member) function exch and for PQ3 you must include the (private member) functions fixUp (Program 9.3) and fixDown (Program 9.4).

• Some hints as to how to implement the insert function for PQ2 may be found by reading about insertion sort (section 6.3). The implementation of PQ4 is very similar to PQ3. The major changes are in how the parent and children positions are computed and in fixDown you must find the maximum of all three children.

• Depending on the machine, compiler, etc. the time to sort 128,000 items using PQ1 could be as high as half an hour so leave enough time to perform your experiment. If you are using a shared system try to avoid running the experiment at a peak usage time. Make sure you have tested your program thoroughly on small inputs before running the whole experiment. You can use the results from small inputs to estimate how long the experiment will take.