Assignment 4

Due by 11:59pm on Monday, 11/26/2018

No demo for this assignment

In this assignment, you will implement a complete heap-based priority queue. In addition to the description of your task below, there is thorough documentation in the file pq.c describing how each function you'll write should behave.

Your work for this assignment will be limited to the file pq.c. In other files, you are provided with some additional starter code that defines the structures you'll be working with and prototypes functions you'll be using and writing. It's important that you don't modify the function prototypes. To help grade your assignment, we will use a set of unit tests that assume these functions exist and have the same prototypes that are defined in the starter code. If you change the prototypes, it will cause the unit tests to break, and your grade for the assignment will likely suffer. Feel free, however, to write any additional functions you need to accomplish the tasks described below.

Implement a heap-based priority queue

Your task for this assignment is to implement a heap-based priority queue. Specifically, in the file pq.c, you must define the struct pq and implement the following functions:

• pq_create() - allocates and initializes a heap-based priority queue
• pq_free() - frees all memory allocated to a priority queue
• pq_isempty() - should tell the user whether a priority queue is empty
• pq_insert() - should insert an element with a specified priority value into a priority queue
• pq_first() - should return the value of the first element in a priority queue
• pq_first_priority() - should return the priority value associated with the first element in a priority queue
• pq_remove_first() - should remove the first element from a priority queue and return its value

Here are some specific notes on how the priority queue you'll implement should behave:

• Your priority queue must be implemented using a heap as the underlying data structure.

• In the priority queue you implement, lower priority values should correspond to elements with higher priority. In other words, the first element in the priority queue should be the one with the lowest priority value among all elements in the collection. For example, your priority queue should return an element with priority value 0 before it returns one with priority value 10.

• Your pq_insert() and pq_remove_first() functions should both have average runtime complexity O(log n), and your pq_first() and pq_first_priority() functions should both have average complexity O(1).

• Your priority queue should not have any memory leaks.

• In lecture, we discussed how you can implement a heap using an array. In dynarray.c and dynarray.h, you are provided with a dynamic array implementation you can use to implement your heap, if you'd like. In addition to this dynamic array implementation, you may implement any additional helper functions you need to make your priority queue work.

Testing your work

In addition to the starter code provided, you are also provided with some application code in test.c to help verify that your functions are behaving the way you want them to. In particular, the code in test.c calls the functions you'll implement in this assignment, passing them appropriate arguments, and then prints the results. You can use the provided Makefile to compile all of the code in the project together, and then you can run the testing code as follows:

make
./test

You can see some example output from a correct solution to the assignment in the file example_output.txt.

In order to verify that your memory freeing functions work correctly, it will be helpful to run the testing application through valgrind.

There is also a more extensive unit test suite for all of the functions you'll write for this assignment included in unittest.c. After running make, you can run these unit tests as follows:

./unittest

There are several unit tests included, and if any unit test failures occur, an error message will be printed out indicating the line number in unittest.c from which the failure originated. There are comments above each test that you can read to more thoroughly understand any given test failure.

Submission

As always, we'll be using GitHub Classroom for this assignment, and you will submit your assignment via GitHub. Just make sure your completed files are committed and pushed by the assignment's deadline to the master branch of the GitHub repo that was created for you by GitHub Classroom. A good way to check whether your files are safely submitted is to look at the master branch of your assignment repo on the github.com website (i.e. http://github.com/OSU-CS261-F18/assignment-4-YourGitHubUsername/). If your changes show up there, you can consider your files submitted.

Grading criteria

To grade your work, the TAs will use the tests in both test.c and unittest.c. Your programs MUST compile and run on flip.engr.oregonstate.edu, so make sure you have tested your work there before you make your final submission, since a program that compiles and runs in one environment may not compile and run in another. Assignments that do not compile on flip will receive a grade of 0. If you do not have an ENGR account, you can create one at https://teach.engr.oregonstate.edu/.

The assignment is worth 100 total points, broken down as follows:

• 5 points: struct pq defines a heap-based priority queue
• 5 points: pq_create() correctly allocates and initializes a heap-based priority queue
• 5 points: pq_free() correctly frees all memory associated with a priority queue (no memory leaks!)
• 5 points: pq_isempty() correctly determines whether a priority queue contains any elements or not
• 5 points: pq_first() correctly returns the value in a priority queue with the lowest priority value
• 5 points: pq_first_priority() correctly returns the lowest priority value in a priority queue
• 30 points: pq_insert() correctly inserts a value into a priority queue with the specified priority and restores the heap property as needed
• 30 points: pq_remove_first() correctly removes the element with the lowest priority from a priority queue and returns its value, restoring the heap property as needed
• 10 points: pq_insert() and pq_remove_first() are both O(log n), and pq_first() and pq_first_priority() are both O(1)

Note that we will only consider changes to pq.c when grading your work. Changes to other files will be ignored.