Assignment 3
Due Friday, April 27



This assignment exercises your knowledge of generics and overloading in Java and C++.

Part 1 of the Assignment (Java)

The Java part of your assignment in Java will be to implement an efficient generic priority queue class, similar to the PriorityQueue generic class defined by the Java API. Your priority queue will must support O(log n) insertion of an arbitrary value into the priority queue, O(log n) removal of the largest element from the priority queue, and constant time lookup of the largest element (without removing it from the queue). Note that the above complexity measures assume that a comparison can be performed in constant time.

You are free to choose the internal representation of the priority queue, although I recommend using a heap, which is the data structure used in heapsort, and is a balanced binary tree with the property that the value associated with a node N is greater than the value associated with any other node in the subtree rooted at N. I provide here an algorithm that represents a heap as an array and implements the add_element and remove_element routines. Although you may use a different representation (such as an actual tree), you cannot use the built-in Java PriorityQueue class and you must be sure that your code has the right asymptotic complexity. Of course, you must write all the code yourself.

Step 1
Review the tutorial on Java generics on the course web page. Also review the PriorityQueue class at the Java API (see the link from the course web page).

Step 2

Implement your generic priority queue class as follows:

Step 3

Implement another class that contains the following static methods.



Part 2 of the Assignment (C++)

Step 1

The code for this step should go into a file called main1.cc. It must compile and run without crashing or throwing exceptions. You should do the following:



Step 2

The code for this step should go into a file called main2.cc. If you modify ptr.h, please put your modified smart pointer header code into a file called ptr2.h. You should do the following:

Submitting your work

Send an email message to Prof. Goldberg (goldberg@cs.nyu.edu) that has the subject line "OOP Assignment 3". Attached to the message should be a zipped folder containing the following:

The zipped folder should have your name on it. Please do not put any executables or example files in the folder.