Programming Assignment 3


The goal of this assignment is to implement a variant form of priority queue capable of supporting updating and removing elements, while maintaining the complexity guarantees of standard priority queues.

Be sure to follow the 311 coding standards.


There are two parts to this assignment:

Pair-programming is allowed if it is true pair programming, i.e., coding done by both partners together, on one computer, switching every 20 minutes or so. The analyses should be done individually.

Implement an Updatable Priority Queue

A standard priority queue, such as priority_queue in the C++ standard library, does not let you remove items after they have been added, except by popping them off when they (eventually) reach the front of the queue.

Further, if the priority of the item is increased or decreased after it is added, there is no way to tell the queue to adjust itself.

Your job is to implement an updatable priority queue, called u_priority_queue. It should mirror the standard priority_queue template class, with a few simplifications, and two extra member functions:

You are not required to support additional template parameters, such as the container in which to store the heap or the comparison function to use. Instead, you should just use a vector (not an array) for the heap, and use operator< to compare values.

Note that updatable priority queues only make sense for compound objects, e.g., tasks with priorities or scheduled times, where the priority is just one part of the value and does not determine the identity of the value. An updatable priority queue of simple numbers would make no sense.

Additional Requirements

In order for remove(T value) and update(T value) to work in O(log N) time or less, an updatable priority queue must be able to

The first part can be done with either a map or hash_map to associate a value with its current location.

A map would provide O(log N) performance, but introduces a conflict:

One alternative would be to require users to specify in the template parameters the ordering predicates for priorities and identities. But this seems a bit annoying to have to do every time.

Therefore, use a hash_map (or unordered_map, if that's what your compiler supports) to map values to heap locations. Then, to store objects of type T in an updatable priority queue, the user just needs to make sure that:

A more flexible updatable priority queue could allow the user to specify template parameters for these functions, but it would not be required.

The second problem is to make changes to locations as cheap as possible. If the hashtable stores just a location, i.e., an integer, then every time a value is moved, the hashtable would have to be accessed and updated. Hashtables are O(1) but they are still much more expensive than simple vector assignments.

The trick, shown on many web sites, is to internally dynamically allocate a pair object containing the value and its location in the heap. Store pointers to that pair in the hashtable and the heap. When you need the location of a value, the hashtable gives you the pair, which gives you the location in the heap. Then, on remove or update, as the pair moves up or down the heap, the location can be updated with a simple assignment to the pair.

As always, when you allocate memory dynamically, you have to remember to deallocate it. That means whenever an item is removed, you need to delete the pair, and when the priority queue is destroyed, it should delete any pairs remaining in it.


Use test_upq.cpp to test your updatable priority queue. This test code builds and tests a u_priority_queue with various data sets.

test_upq.cpp does two things:

The event part is ready to run, as soon as you have a working priority queue. The election part requires you to define some additional classes to model the domain of candidates and votes.

The code and sample data files are in

The Event Tests

The event testing part of test_upq.cpp is designed to help you uncover common bugs in implementing this kind of container. The code creates simple Event objects. These objects have just an id number and a priority. The class is defined in event.hpp and event.cpp. operator<(const Event &e1, const Event &e2) is defined to compare event priorities, while a hashing function is defined to use event ids. The number of events queued is controlled by MAX_QUEUE. It's set to 6, which is enough to uncover most common bugs in implementing heaps.

The hashing function declaration is specific to g++ 3.4.2, which is used in Dev-C++. If you are using another compiler, you will need to find out how hashing functions are defined for classes in that system.

test_upq.cpp should be very helpful when you develop and debug your queue, because it runs tests starting with very small data sets that can be analyzed by hand. test_upq.cpp illustrates an important point about testing code. Testing code should catch errors itself, rather than printing data for a (fallible) human to inspect for errors.

The Election Test

After the event tests pass, uncomment the two lines in test_upq.cpp for doing elections. Declare the function testElection() in test_election.hppand implement it in test_election.cpp. You also need to define a class to represent a candidate, with the candidate's name and current vote tally. Use the Event class as a model.

The call testElection(int numSeats, const char* nameFile, const char *votesFile) should

Two sample data files are provided.

Here's some sample output:

After precinct 1, leader is Toomey:550
After precinct 2, leader is ...

Top 9 vote-getters are:
1: xxxx:2729
2: ...
9: ...

What to Hand in

Submit a zipped or tar-gzipped archive of one directory called last-name_first-initial_pa3, containing:

If you worked alone, call the archive (use .tgz for tar-gzipped files). Example:

If you pair-programmed, call the archive (use .tgz for tar-gzipped files). Example:

Important! Make sure your archive meets the general code submission requirements.

Every source file should have an opening header comment of the following form:

// Filename: u_priority_queue.hpp (or whatever)
// EECS311 PA3 solution: Updatable priority queue
// Date: May 9, 2007
// Authors: Dan Kornhauser, Stephen Tarzia
// Programming sessions: 5/2/07: 4-6pm; 5/6/07: 3-6pm; 5/8/07: 10am-noon
// Except for code provided by the instructor or textbook, this code was written
// solely by the authors listed above, and not copied from another student
// or external source.

Email your code, in a compressed archive, to me with the Subject line EECS 311 PA3.

Valid HTML 4.01 Strict