Due

Objectives

• to implement a priority queue

Assignment

• PriorityQueue() to create an empty queue;
• int getSize() to return the number of items currently on the queue;
• void addItem(Object item, int pri) to add the given item with the given priority to an existing priority queue (provided that the item is not already on the queue);
• Object removeItem() to remove and return the object with the lowest priority (provided that the queue is not empty); and
• void changePriority(Object item, int newPri) to change the priority of an item that is already on a priority queue (provided that the item is, in fact, on the queue).

Suggestions

In order for changePriority to work in O(log n) time, you will need some way of finding items in the heap. You can do this by maintaining an auxilliary structure that maps items to indices in the heap. It would be best if lookups in that table operate in O(1) time under reasonable assumptions.

Files

• PQueueTest.java

Grading

• Use your own heap code to implement the priority queue. Using existing classes (from JCF or STL, for example) is OK for any auxilliary structures or for storage of the heap elements, but do not use such code to implement the heap algorithms.
• Your methods should have reasonable worst case running times.
• It should be easy to use your priority queue with different kinds of objects. For Java, this means that you should use the Object class. In C++ you should use typedefs or templates. You may make reasonable assumptions about the objects placed on the queue (for example, you may assume they have an equals method), but you must document those assumptions.

The following files were used for grading. The main method implements Prim's MST algorithm on a graph read from standard input. The .dat files are the inputs.

• main.cpp
• Main.java
• sort.dat
• sort2.dat
• mst.dat

Submissions