Description
Background
Since this is the last week of classes, there are 3 options for project #07. Your options are defined by the
following pseudo-code:
There will be 4 sets of submissions available on Gradescope, one for each option. After the due date, you
*must* also submit an online google form to inform us of what we should grade. If you do not submit this
form before Monday, 12/9 @ 12noon, we will assume you have nothing to submit for project #07. Link to
google form: https://bit.ly/cs251-project07 .
7
minqueue v2
Dijkstra’s algorithm requires a priority queue that returns the next vertex to process, based on the vertex
with the shortest distance from the starting vertex. In project #06, a minqueue<TKey, TValue> class was
defined in “minqueue.h” to provide this functionality. The implementation was easy to understand, but
inefficient.
Your assignment is to provide an O(lgN) implementation based on a min-heap data structure. As discussed
in class (days 39 and 40), this is a tree-based data structure implemented using an array. However, our
minqueue needs to extend the traditional min-heap to allow O(1) or O(lgN) lookup of keys — as required by
Dijkstra’s algorithm. Recall that Dijkstra’s algorithm, when it finds a shorter path, needs to update an existing
(key, value) pair in the queue, and reorder the queue appropriately.
Here is the design of the minqueue<TKey, TValue> class that you must implement. You must implement
this design as given, you cannot the function names, parameters, or return values. The comments provide a
summary of each function:
/*minqueue.h*/
//
// Min queue that stores (key, value) pairs using a min-heap
// implementation. When pop is called, the key from the
// (key, value) pair with the smallest value is returned; if
// two pairs have the same value, the smaller key is returned.
// Push and pop have O(lgN) time complexity.
//
// << YOUR NAME >>
//
// Original author: Prof. Joe Hummel
// U. of Illinois, Chicago
// CS 251: Fall 2019
// Project #07
//
#pragma once
#include
#include
#include
#include
using namespace std;
template
class minqueue
{
private:
CS 251 : https://www.cs.uic.edu/~i251/ Page 3 of 7
public:
//
// default constructor:
//
// Queue has a max capacity for efficient implementation.
// This max capacity must be specified at queue creation.
//
minqueue(int capacity)
{
//
// TODO:
//
}
//
// fill constructor:
//
// This allows for the efficient O(N) construction of
// a queue with an initial set of keys, all with the same
// initial value. The max capacity of the queue is
// set to the # of keys provided for initialization;
// it is assumed the keys are in ascending order.
//
minqueue(vector keys, TValue initialValue)
{
//
// TODO:
//
}
//
// destructor:
//
virtual ~minqueue()
{
//
// TODO:
//
}
//
// empty:
//
// Returns true if empty, false if not.
//
bool empty()
{
}
//
CS 251 : https://www.cs.uic.edu/~i251/ Page 4 of 7
// push:
//
// Inserts the given (key, value) pair into the queue such that
// pop always returns the pair with the minimum value. If the
// key is *already* in the queue, it’s value is updated to the
// given value and the queue reordered. If the key is not in
// the queue, the (key, value) pairs is added and the queue
// reordered.
//
// NOTE: if two keys have the same value, i.e. (key1, value) and
// (key2, value), then those pairs are ordered into ascending value
// by their key.
//
void pushinorder(TKey key, TValue value)
{
//
// TODO:
//
//
// we need to insert a new (key, value) pair but the queue is full:
//
//if (…)
//{
// throw runtime_error(“minqueue::pushinorder: queue full”);
//}
//
}
//
// front:
//
// Returns the key at the front of the queue; does *not* pop the
// (key, value) pair. Throws a logic_error exception if the queue
// is empty.
//
TKey minfront()
{
if (empty())
{
throw logic_error(“minqueue::minfront: queue empty”);
}
//
// TODO:
//
}
//
// pop:
//
// Pops and discards the (key, value) pair at the front of the queue.
CS 251 : https://www.cs.uic.edu/~i251/ Page 5 of 7
// Throws a logic_error exception if the queue is empty.
//
void minpop()
{
if (empty())
{
throw logic_error(“minqueue::minpop: queue empty”);
}
//
// TODO:
//
}
};
Implementation details
Your implementation will need 2 data structures. The 1st is an array to store the min-heap tree, and this
should be an array of (key, value) pairs. Keep in mind the minqueue is ordered by value; if two pairs have the
same value, then order by key.
The 2nd data structure enables O(1) or O(lgN) lookup to see if a key is already in the minqueue, and if so,
where it is. You cannot search the array since it’s not ordered by key — linear search would be the only
option, and that’s too slow. The choice of the 2nd data structure is up to you, but it needs to enable O(1) or
O(lgN) lookup of a key’s position.
The algorithms for push and pop are well-known. These are discussed in zybooks, and here’s another
reference I also find helpful:
Pop: https://www.algolist.net/Data_structures/Binary_heap/Remove_minimum
Push: https://www.algolist.net/Data_structures/Binary_heap/Insertion
As elements are pushed, popped and swapped, don’t forget to update data structure #2. Note that our
version of “push” needs to be more sophisticated than a traditional min-heap since the key may already be in
the queue. In this case, the recommended approach is to delete the existing (key, value) pair, and then do a
traditional push of a new (key, value) pair. Here’s the pseudo-code for deleting a (key, value) pair from *any*
position in minqueue. This is different than pop, which only deletes the first element:
delete(key, value):
1. Let p = position of (key, value) pair in array
2. If p denotes the last position in the queue, reduce # of elements by 1 and return;
3. Move last pair into position p
4. Reduce # of elements by 1
5. Let (K, V) be the pair at position p. Does K have a parent? If so, compare values and see if (K, V)
CS 251 : https://www.cs.uic.edu/~i251/ Page 6 of 7
should sift upward… If sift occurs, update p to new position and repeat this step.
6. Let (K, V) be the pair at position p. Does K have children? One child or two? If just one child,
compare values and sift downward if necessary. If two children, compare against the smaller of
the two children, and sift download if necessary; if the children have the same value and a sift
download should occur, swap with the child with the smaller key. If sift occurs, update p to
new position and repeat this step.
7. Return.
For initial testing, I would recommend using project #06 — your implementation should be compatible with
the minqueue used in project #06. A Codio project is provided with the initial “minqueue.h” file; see “cs251-
project07-minqueue-v2”. If you prefer to work outside of Codio, the “minqueue.h” file is also available on the
course web page under “Projects”, “project07-files”.
Requirements
1. Follow minqueue.h design as given.
2. Push, pop and front must be O(lgN) in time.
3. Data structure #1 must be an array of (key, value) pairs.
4. Data structure #2 must enable O(1) or O(lgN) lookup of key’s position in data structure #1.
Program submission
If you are submitting an earlier project, look for the appropriate “resubmission” site(s) on Gradescope;
note that Project #05 has two submissions (one for the Hash function, and one for the program). After
submission, you *must* also submit an online google form telling us what to grade: https://bit.ly/cs251-
project07 .
If you are submitting a minqueue implementation for project #07, submit your “minqueue.h” file on
Gradescope to “Project 07 – minqueue v2”. Unlike previous projects, we will not auto-grade this one. Your
submission will be checked to ensure that it compiles, but that’s it. Any code that doesn’t compile won’t be
graded. Grading based on 90% correctness, 10% style. After submission, you *must* also submit an online
google form telling us what to grade: https://bit.ly/cs251-project07
Policy
Late work is *not* accepted. All work submitted for grading *must* be done individually. While we encourage you
to talk to your peers and learn from them (e.g. your “iClicker teammates”), this interaction must be superficial with
regards to all work submitted for grading. This means you *cannot* work in teams, you cannot work side-by-side, you
cannot submit someone else’s work (partial or complete) as your own. The University’s policy is available here:
CS 251 : https://www.cs.uic.edu/~i251/ Page 7 of 7
https://dos.uic.edu/conductforstudents.shtml .
In particular, note that you are guilty of academic dishonesty if you extend or receive any kind of unauthorized
assistance. Absolutely no transfer of program code between students is permitted (paper or electronic), and you may
not solicit code from family, friends, or online forums. Other examples of academic dishonesty include emailing your
program to another student, copying-pasting code from the internet, working in a group on a homework assignment,
and allowing a tutor, TA, or another individual to write an answer for you. It is also considered academic dishonesty if
you click someone else’s iClicker with the intent of answering for that student, whether for a quiz, exam, or class
participation. Academic dishonesty is unacceptable, and penalties range from a letter grade drop to expulsion from the
university; cases are handled via the official student conduct process described at
https://dos.uic.edu/conductforstudents.shtml .
CS 251 : https://www.cs.uic.edu/~i251/ Page 8 of 7