Assignment 10: Priority Queue in C

Note the unusual due date.

Objectives

For this assignment, you will:

• Gain experience programming in C
• Gain experience working with pointers and structs
• Gain experience using a header file

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 key and a priority. The priority queue will allow the user to insert pairs, 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 implemen- tation, all of the functions must work correctly in logarithmic time. In other words, doing a linear search for a key 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 functions prototypes declared in the header file (in this case, pqueue.h). The functions declared in the header file are as follows:

pqueue init(pqueue *self)
pqueue* pqueue push(pqueue *self, int key, int priority)
pqueue* pqueue pop(pqueue *self)
pqueue* pqueue top(pqueue *self, int *key, int *priority)
unsigned int 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

Submitting Your Work

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

make package

Then submit that directory by running:

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

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

Some hints

• Try and follow the outline from our existing binary heap in Java.
• As always, try and code incrementally, testing and compiling as you go. Don’t be afraid to write some unit test functions (or even add new test.c/h files to hold tests).
• In fact, you can probably save time by starting with your unit tests: this will force you to think about your design without coding too much, and it will save you a lot of debugging time in the end.
• Use fprintf to help you debug (but remove these when you submit your final version).
• Leave plenty of time for debugging!