Module 2: Priority Queues
Studio
Bad Priority Queue Implementations
Authors: Tim Heyer and Ron Cytron
Introduction
In lecture, you've learned several different data structures that can be used to implement a priority queue and the pros/cons for each.
In this studio, you will implement two of these priority queues and examine where each shines over the other.
For reference, you should review the lecture slides on PQs as Unordered Lists and PQs as Ordered Arrays.
- Begin by opening the studio3 package in the studios source folder of your repository.
- Find and open PriorityQueue.java and examine the interface.
- Name three data types that could serve as T.
- Look at the Comparable interface.
- Find a class there that you don't know yet, and visit it to see
how it implements compareTo(…).
- The compareTo(…) method is of great interest for
this and subsequent assignments.
Given the call a.compareTo(b), which of the
following is true?
- The call returns -1 if a is less-than b
- The call returns 0 if a is equal-to b
- The call returns 1 if a is greater-than b
Discuss this among yourselves and present your answer to a TA.
- Open the UnorderedList.java class, complete the methods, and run the unit tests.
- Open the OrderedArray.java class, complete the methods, and run the unit tests.
- Open the UnorderedListExperimentInsert.java class.
- Arrange for reset() to prepare an unordered list with n entries.
The easiest way to do this is to call your own insert(T thing) method.
- Arrange for run() to insert one entry.
- Run the experiment to collect the output and open the .csv file
in Excel.
What does the asymptotic complexity of insert(T thing) appear to be?
- Open the UnorderedListExperimentExtractMin.java class and complete it accordingly.
- Run the experiment to collect the output and open the .csv file
in Excel.
What does the asymptotic complexity of extractMin() appear to be?
- Repeat this activity with OrderedArrayExperimentInsert.java and OrderedArrayExperimentExtractMin.java.
- Present your results to a TA before you are signed for this studio.
Submitting your work (read carefully)
- If your studio contains a feedback.txt file, respond to
the questions and supply any requested information.
- You must commit all of your work to your repository and push it. It's best to do this
from the top-most level of your repository, which bears your wustl key.
Last modified 09:46:23 CDT 22 August 2016