Priority Queues
Designing and analyzing priority queues.
Priority queues are a fundamental building block for many real-world algorithms. For instance, if we only need to show the first 10 autocomplete matches in a specific order, a priority queue can be more efficient than sorting the entire list of all matches. Or, if we’re implementing a map navigation algorithm, a priority queue allows dynamic updates to the next-shortest path as the algorithm discovers new roads. Or, if we’re designing a worldwide web analytics dashboard, a priority queue can track statistics like the accessibility of the most commonly-visited web pages.
In this project, we will compare 4 implementations of priority queues to build a web analytics dashboard for tracking the occurrence of Web Content Accessibility Guideline recommendations. By the end of this project, students will be able to:
- Design and implement multiple data structures to solve complex problems.
- Analyze and compare implementation runtimes and optimizations.
In the next project, we’ll also use your priority queues as a building block for shortest paths.
Can I work with someone else on this project?
Although this project requires an individual submission, you may find it useful to discuss overarching ideas with your classmates. Our primary rule is that we ask that you do not claim to be responsible for work that is not yours. If you get some help from someone else or from an online resource, cite it. I believe that there is a lot of value in learning from others so long as you do not deprive yourself (or others) of the opportunity to learn.
We are comfortable doing this because each submission in this class comes in the form of a video that you record. Your video is a demonstration of everything that you learned throughout the process of working on an assignment. Our goal is for students to support each other and find community through this course. The real advantage of taking a course on-campus at a university is to be able to connect with others who share common interests in learning.
What am I submitting at the end of this project?
Satisfactory completion of the project requires one Canvas submission including: a video-recorded individual presentation, a link to your filled-out slide template for Priority Queues and a link to your src/main/java/minpq
folder on GitLab from your projects repo that addresses all deliverables (in green).
The project instructions contain a lot of details to provide context, clarify common confusions, and help students get started. Your Canvas submissions only need to address tasks that are described in green callouts like this one.
Your video presentation should meet the following requirements:
- Your presentation should not be much longer than 8 minutes (9 minutes maximum) and should include your voiceover. (Your video is appreciated but not necessary.)
- Your video presentation must include or use our provided slide template for Priority Queues. This is done intentionally to help guide you toward the correct solution.
- After submitting to Canvas, add a submission comment linking to your slides or document and a link to your
src/main/java/minpq
folder on GitLab. Remember tocommit
andpush
to Gitlab and check the associated status for your latest Pipeline is a green checkmark! Please be sure to check access permissions on your slides and video, so any TA can view your work.
Students are expected to follow Washington state law on the Student Conduct Code for the University of Washington. In this course, students must:
- Indicate on assignment submissions any assistance received, including materials distributed in this course.
- Not receive, generate, or otherwise acquire any substantial portion or walkthrough for an assignment.
- Not aid, assist, attempt, or tolerate prohibited academic conduct in others.
Within the provided slide template, you must cite any external sources you used, either through collaboration or online resources. If you consulted any Generative AI on this project, you must include all prompts and outputs. Online sources should be cited with a simple link. Collaboration with peers must include names and the extent of that collaboration. The more detail, the better!
Submitted work that is not consistent with sources will require makeups in Office Hours.
Priority queue interface
The MinPQ
interface represents a priority queue that affords access to minimum-priority elements. Priority values are extrinsic to each element: rather than relying on a compareTo
method, priority values are specified as arguments to the add
and changePriority
methods.
void add(E element, double priority)
- Adds an element with the given priority value if the element is not already in this priority queue.
boolean contains(E element)
- Returns true if the given element is in this priority queue.
E peekMin()
- Returns the element with the minimum priority value.
E removeMin()
- Returns and removes an element with the minimum priority value.
double getPriority(E element)
- Returns the priority value for the given element if it is present.
void changePriority(E element, double priority)
- Updates the given element’s associated priority value.
int size()
- Returns the number of elements in this priority queue.
peekMin
and removeMin
should throw a NoSuchElementException
if the priority queue is empty. getPriority
and changePriority
should throw a NoSuchElementException
if the element is not present.
The interface also defines two default methods that rely on implementations of the above methods.
void addOrChangePriority(E element, double priority)
- Adds an element with the given priority value if it is not already present. Otherwise, updates the priority value of the existing element.
if (!contains(element)) { add(element, priority); } else { changePriority(element, priority); }
boolean isEmpty()
- Returns true if this priority queue contains no elements. Returns whether
size() == 0
. List<E> removeMin(int numElements)
- Returns and removes up to the given number of lowest-priority elements.
A MinPQ
cannot contain duplicate elements. However, different elements can have the same priority value. peekMin
and removeMin
may return any element with the minimum priority value.
Here’s a small example test showing how to use the MinPQ
interface with the DoubleMapMinPQ
reference class included in the project. Try this example yourself by writing a new test case in the MinPQTests
class. You can write additional test cases like this to assist in debugging.
@Test
void compareSimple() {
MinPQ<String> reference = new DoubleMapMinPQ<>();
for (int i = 1; i < 7; i++) {
reference.add("" + i, i);
}
MinPQ<String> testing = createMinPQ();
for (int i = 1; i < 7; i++) {
testing.add("" + i, i);
}
// Call methods to evaluate behavior.
reference.changePriority("3", 0.0);
reference.changePriority("1", 7.0);
testing.changePriority("3", 0.0);
testing.changePriority("1", 7.0);
// Assert that the different PQ's contain elements in equivalent order
while (!reference.isEmpty()) {
assertEquals(reference.removeMin(), testing.removeMin());
}
assertTrue(testing.isEmpty());
}
The compareSimple
test will be used in your code tracing deliverables in this specification. We recommend that you add this to MinPQTests
.
Why not just implement Java's PriorityQueue interface?
The java.util
standard library includes a binary heap PriorityQueue
class. Here are three reasons why we can’t implement Java’s PriorityQueue
class in this project.
PriorityQueue
is a class- We can’t implement the
PriorityQueue
class because it’s a class, not an interface. Although the Java developers designedSet
,Map
, andList
as interfaces, priority queues are so commonly associated with binary heaps that the Java developers broke the pattern and definedPriorityQueue
as a class. PriorityQueue
relies oncompareTo
- By default,
PriorityQueue
uses elements’compareTo
method to define the priority of an element. For example, the priority of the string “A” is less than “B” because “A” precedes “B” in the alphabet. This makesPriorityQueue
great for sorting objects, but not great for applications like shortest paths. PriorityQueue
disaffords changing priority value- The fact that
PriorityQueue
uses elements’compareTo
methods reveals a hidden disaffordance. To change the priority of an object inPriorityQueue
, we need to remove the element from the priority queue and then re-insert it. This workaround is not only inconvenient, but also inefficient and prone to bugs.
PriorityNode
Java collections typically only specify a single data type as in ArrayList<String>
. But a MinPQ
needs to keep track of each element as well as its associated priority value. We could do this by creating two lists: an ArrayList<T>
for elements and an ArrayList<Double>
for each element’s priority value. However, this approach requires us to ensure the state of both lists are always the same, which introduces additional complexity that makes the code harder to maintain and more brittle or susceptible to future bugs.
The PriorityNode
class includes two fields representing an element
together with its priority
value so that it can be used in a Java collection.
List<PriorityNode<String>> elements = new ArrayList<>();
elements.add(new PriorityNode<>("example", 0));
Two PriorityNode
objects are considered equal if and only if their elements are equal. Priority values are not checked for equality.
How will this property of PriorityNode equality help you implement MinPQ?
MinPQ
does not allow duplicate elements, but does allow duplicate priority values. When using Java collections such as a List
, methods like List.contains
or List.remove
will call the objects’ equals
method to check for equality. The following contains
call will return true
, and the remove
call will successfully remove the priority node even though their priority values are different.
elements.contains(new PriorityNode<>("example", 1));
elements.remove(new PriorityNode<>("example", 2));
Reference implementation
The project code includes a working DoubleMapMinPQ
. This implementation is called “double map” because it combines the runtime benefits of two maps to solve the problem efficiently. The two maps work together to help achieve sublinear (logarithmic or better) runtime for every operation.
NavigableMap<Double, Set<E>> priorityToElement
- Associates each unique priority value to all the elements with that priority value. Returning a minimum-priority element involves finding the set of minimum-priority elements and picking any element from that set.
Map<E, Double> elementToPriority
- Associates each element with its priority value in order to speed-up
contains
andchangePriority
.
The state of both maps is synchronized across all methods. Any change to one data structure also requires a change to the other data structure.
Design and implement
Design and implement 3 implementations of the MinPQ
interface.
Make sure to pass all the tests
for UnsortedArrayMinPQ
, HeapMinPQ
, and OptimizedHeapMinPQ
, push your code to Gitlab, and check that the associated status for your latest Pipeline is passing. Include a link to the passing pipeline of your projects repository in the provided slide template.
UnsortedArrayMinPQ
Elements are added to an ArrayList
in any order. Many operations may need to scan over the entire list.
To approach this implementation, consider the following hints:
- Identify, at a high level, what
ArrayList
methods you can use to implement the methods required by theMinPQ
interface. - For each method you write, determine if you can easily locate the
PriorityNode
and its corresponding element you need to update, remove, or return. - Recall that two
PriorityNode
objects are considered equal if and only if their elements are equal. How can you make use of this property? - Reference the
PriorityNode
class as needed to utilize its getters and setters.
HeapMinPQ
A standard binary heap priority queue that delegates all method calls to java.util.PriorityQueue
. In other words, each MinPQ
operation is implemented by calling the underlying PriorityQueue
. This class contains only one field assigned to an instance of PriorityQueue
. Our solution only uses 1-3 additional lines of code for most methods.
To approach this implementation, consider the following hints:
- Read through the
PriorityQueue
documentation to identify which methods you can use to implement the methods required by theMinPQ
interface. - Recall that the ‘elements’ of our
PriorityQueue
arePriorityNode
objects. This may require extra work to achieve the desired return type, such as the use of getters. - Recall that two
PriorityNode
objects are considered equal if and only if their elements are equal. How can you make use of this property? You may find that your approach overlaps withUnsortedArrayMinPQ
.
Trace through the compareSimple
test for HeapMinPQ
by adding it to MinPQTests
. First, without walking through the code, create a diagram of pq
that showcases the state of testing
after inserting all nodes. Then, explain how your changePriority
method works to update the priorities for elements “3” and “1”. You must explain in detail why your approach works and discuss all state changes in the context of the test case input and output. Lastly, explain why testing
and reference
share the same removal order to allow for assertEquals
to always return true
.
Once you explain a method one time, you do not need to repeat an explanation of its operations in your code trace.
We recommend that you utilize your visual diagram when explaining changePriority
to ensure continuous explanations in connection to the compareSimple
test.
OptimizedHeapMinPQ
A optimized binary heap priority queue supported by a HashMap
that associates each element with its array index to speed-up contains
and changePriority
. In other words, our heap, represented through an array, holds priority nodes organized by priority value. The HashMap
acts as an “address book” for the indices of each priority node, helping us locate nodes within the heap.
Use this MinPQ.java class as a reference.
- Skim MinPQ.java: What do you notice will work for our
MinPQ
interface? What needs to change?- Begin by understanding the fields and constructor for the reference
MinPQ
. At what index is the first element found? Accordingly, what indexing calculations are being used? How does this connect back to your understanding of binary min-heaps?
- Begin by understanding the fields and constructor for the reference
- Identify methods in the
MinPQ
class that are most similar to ourMinPQ
interface.- For each corresponding method you find, pay close attention to the additional helper methods referenced. Consider replicating these given their repeated usage.
- Also pay close attention to the conditionals used and general logic to ensure that an operation is performed at the right time, and leads to the intended state change. What edge cases do you need to consider?
- Adapt the code to implement our interface, without a
HashMap
. Make sure all tests pass before proceeding.- Descriptive variable names are crucial! The reference class can be difficult to parse from its shorthand variable-naming and we discourage this.
- Optimize the code by adding a
HashMap
synchronized to the state of the elements in the array.- Note that any operation which requires a change in
elements
necessitates a corresponding change toelementsToIndex
. - Determine what methods benefit from knowing the index at which an element is stored.
- Note that any operation which requires a change in
Trace through the compareSimple
test for OptimizedHeapMinPQ
by adding it to MinPQTests
. First, without walking through the code, create diagrams for both elements
and elementsToIndex
that showcase the state of testing
after inserting all nodes. Then, explain how your changePriority
method works to update the priorities for elements “3” and “1”. You must explain in detail why your approach works (across all helper methods) and discuss all state changes in the context of the test case input and output. Lastly, explain why testing
and reference
share the same removal order to allow for assertEquals
to always return true
.
Once you explain a method one time, you do not need to repeat an explanation of its operations in your code trace.
We recommend that you utilize your visual diagram when explaining changePriority
to ensure continuous explanations in connection to the compareSimple
test.
Don’t copy and paste code! Most of the time, we will need to make many changes, and we might introduce subtle bugs when we copy code that we don’t fully understand. Instead, rewrite the code in your own words after making sense of the purpose of each line. We often don’t need all the lines of code, and the code can be rewritten in ways that are more suitable for the problem at hand.
Analyze and compare
Asymptotic analysis
Give a big-theta bound for the worst-case runtime of the removeMin
and changePriority
methods for each implementation, including DoubleMapMinPQ
, with respect to N, the size of the priority queue. Explain the worst case and the runtime of each implementation in a couple sentences while referencing the code. You must use the assumptions we provide below for the runtime analysis.
For all array-backed data structures, ignore the time it would take to resize the array.
java.util.PriorityQueue
is implemented using an array-representation binary heap that
provides O(log(n)) time for the enqueuing and dequeuing methods (
offer
,poll
,remove()
andadd
); linear time for theremove(Object)
andcontains(Object)
methods; and constant time for the retrieval methods (peek
,element
, andsize
).
- Java’s
HashSet
andHashMap
are implemented using resizing separate-chaining hash tables where the number of buckets is always similar to the size. Assume that the hash function evenly distributes elements across the buckets in the underlying array.
The Java implementations include a further optimization.
- Tree bucket optimization
- When the size of a bucket exceeds 8 elements, the separate chain is automatically converted from a linked list to a red-black tree.
Explain the impact of tree bucket optimization assuming an even distribution of elements across the underlying array. Does the tree bucket optimization help, hurt, or not affect the asymptotic analysis given our assumptions?
Note that this deliverable should be considered in the context of using a HashMap
and its respective runtimes, as seen in DoubleMapMinPQ
and OptimizedHeapMinPQ
.