Note the unusual due date.

Objectives

For this assignment, you will:

Description

In this assignment, you will create a priority queue. You should construct a correct, robust, and elegant data structure. You may want to write a small program to test it, but the product will be just the header file and the implementation file for pqueue named, naturally enough, pqueue.h and pqueue.c. This will also give you some practice in reading and using documentation.

We want to build a priority queue that stores pairs of integers. Each pair consists of a value and a priority. The priority queue will allow the user to insert pairs and to remove the pair with the lowest priority. A struct has already been defined for you to store the pair of integers in the priority queue. Also, you must check all preconditions and handle them as specified in the documentation provided in pqueue.h.

Classes

The pqueue.h header file You will code your pqueue based on an implementation that uses a heap-ordered array like that in the class VectorHeap from Bailey’s structure library (see the source code on the handouts page). In your implementation, all of the functions must work correctly in logarithmic time. In other words, doing a linear search for a value across an array is not permitted.

It is typical to create an identically named .c file (in this case, pqueue.c) that contains the implementation for each of the function prototypes declared in the header file (in this case, pqueue.h). The functions declared in the header file are as follows:

void init_pqueue(pqueue *self)
pqueue* pqueue push(pqueue *self, int value, int priority)
pqueue* pqueue pop(pqueue *self)
pqueue* pqueue top(pqueue *self, int *value, int *priority)
size_t pqueue size(pqueue *self)
bool pqueue empty(pqueue *self)

Full descriptions of these methods can be found in pqueue.h, and you will need to implement them to the specifications given. You should compare the design of this priority queue with the design of the stack example from class.

Getting Started

  1. Before you begin make sure you understand how a heap based priority queue works by carefully reading the implementation in Bailey’s library.
  2. Read over the stack implementation example from class to get a feel for how “objects” work in C.
  3. When you are ready create a new C file called pqueue.c in the src directory. This is where you will implement all of the functions. You may (and should) add additional helper functions to pqueue.c.

Grading

Criterion Points
Functionality of priority queue 10
Properly checking preconditions 4
Appropriate comments 2
Style and formatting 2
General correctness 2
Submitted correctly 1

Submitting Your Work

Use the makefile to create a submission directory on your desktop by running:

make package

Then submit that directory by running (actually you can skip the make package step because it will be done automatically):

make submit

If you need to submit manually, it will look like:

/common/cs/cs062/bin/submit cs062 asg09 ~/Desktop/PackageName

This will be the approach we will take for all of our C submissions.

Some hints