Description
Unformatted Attachment Preview
Project 4 – Priority Queue (BST)
CS 251, Spring 2024
In this project, we will continue building our own version of data structures. By the end of this
project, you will…
●
●
●
Have created a templated binary search tree
Designed a particular implementation of a priority queue
Implemented multiple traversals through a binary search tree
Restrictions
●
●
●
●
You may not include additional C++ libraries to implement prqueue.
○ The only included libraries are (for as_string) and
(for debugging).
○ You may (and should) include STL libraries to write tests.
Files:
○ You may modify prqueue_tests.cpp freely.
○ You may also modify prqueue_main.cpp, which is not being submitted.
○ You may modify prqueue.h only to add additional private member functions.
You may not add additional member variables, or additional public member
functions.
○ You may not modify prqueue_solution_stub.h. This is only on zyBooks,
and is only for compiling against the solution on zyBooks.
The same memory restrictions as Project 3 apply. That is, memory errors will result in a
0 score on the test suite that hits them; and memory leaks are a flat score item.
You will need to use classes, pointers, and new. Do not use malloc or NULL, we’re not
writing C.
Logistics
This project is larger, and runs through spring break. As such, we are splitting the project into
two parts. The first part will be due before break, and the second part will be due after break.
The two parts, together, are worth 1 project in the overall course grade. Part 2 cannot be
completed without Part 1.
Part 1 (35 points)
Due:
●
Gradescope: Friday 3/15
○ prqueue.h
○
prqueue_tests.cpp
Part 2 (65 points, Part 1 is a required prerequisite)
Due:
●
●
Gradescope: Tuesday 4/2
○ prqueue.h
○ prqueue_tests.cpp
Grace tokens (will be created after break)
Testing
We will continue to require you to write tests for your data structure. We’ll be taking the same
approach as Project 3: we have many buggy implementations, and you’ll be writing tests that
expose these buggy implementations!
You’ll receive credit for each buggy implementation that fails your tests. This will happen when
you submit to Gradescope. Keep in mind that the correct implementation must pass your tests
to receive any credit – no writing EXPECT_TRUE(false), for example. To aid you in checking
your own test cases, we’ve provided a solution “object file” in zyBooks: prqueue_solution.o.
This object file provides instantiations of the solution implementation for prqueue and
prqueue.1 You will be able to test with values of those types, but not others.
In zyBooks, use make run_solution_tests to run your tests on the course staff’s correct
solution.
In Part 1, the tests skip numbers. This is intentional, some of the broken solutions rely on
behavior from Part 2.
Memory Safety & valgrind
The same requirements apply to this project as for Project 3: your programs may not have any
errors reported by valgrind. We aren’t managing pointers as values this time, but we still need to
be careful with the nodes themselves.
1
For technical reasons related to template classes and .h files, along with the need to hide the solution
implementation, the solution compilation is rather hacky.
Priority Queues
We’ve talked about the queue ADT before, which processes elements in the order in which they
were received: First-In, First-Out (FIFO). We also observed that this model isn’t appropriate for
a lot of applications, such as hospital triage. The hospital wants to see patients with more critical
injuries before others with less serious needs. The priority queue ADT is a way of describing
these operations.
A priority queue is similar to a queue or a stack, where we can put elements in, and get them
out. Unlike a queue/stack, each element also has a priority value, which is a number. For
example, a hospital emergency department might use the Emergency Severity Index. A patient
who requires immediate life-saving care would have a priority of 1; while a patient who would be
fine for a while might have a priority of 4. This means that lower priority values should be seen
first.
In Part 1, we will assume that we will never have to handle two elements with the same priority
value. In Part 2, we will modify our Part 1 implementation to handle duplicate priorities!
Binary Search Tree as Priority Queue
The priority queue ADT can be implemented in many ways: an array, a vector, linked list, etc.
We’re going to use a binary search tree on the priorities to allow us to quickly find the element
with the lowest priority, barring the worst-case performance.
For example, for patients that arrive in this order:
●
●
●
●
●
●
“Dolores” with priority 5
“Bernard” with priority 4
“Arnold” with priority 8
“Ford” with priority 2
“Jasmine” with priority 6
“Carlos” with priority 11
Our BST would look like this:
This is an incomplete diagram and does not show all the pointers in use.
The order in which elements would be dequeued is: Ford, Bernard, Dolores, Jasmine, Arnold,
Carlos.
Part 1
Templates
Our prqueue is templated, which allows us to make a prqueue that stores integers, strings, or
any type as the value by writing only one class definition. We can create a prqueue similar to a
vector, by providing the template parameter:
prqueue pq;
We can use values of type T like any other type. When the program is compiled, the compiler
will make sure that whatever type replaces T supports all the operations we use with it.2
Task: Testing
In Project 3 (and 2), course staff used STL containers to help write their tests, such as deque.
This let us take advantage of STL functions to write large tests: we didn’t have to hardcode the
expected values for 100 items.
In this project, we highly recommend using STL containers (vectors and maps) to help write
your tests. One way of viewing a prqueue is as a map from priorities to values. This gets us the
sorted order of priorities for free! This is also straightforward to extend to duplicates in Part 2, by
using a vector as the map value instead.
For example, to test as_string, we might go through the following steps:
●
●
●
●
Generate the data for inserting into the prqueue.
Use a map as the “source of truth”, and insert the data into the map and prqueue.
Call a function that converts the map to the prqueue::as_string format.
Compare the string that results from the map to the actual as_string.
template
string map_as_string(const map& m) {
ostringstream ss;
for (const auto &e : mp) {
int priority = e.first;
vector values = e.second;
for (size_t j = 0; j < values.size(); j++) {
We’re omitting a lot of details here. If you’re curious, see zyBooks Ch. 31, or LearnCPP 13.11. “Any
type” is inaccurate – it needs to be copy-constructible and support
Purchase answer to see full
attachment
