Alternate Priority Queue Implementations

Introduction

Both self-balancing binary trees and heaps are reasonable data structure choices for the Priority Queue ADT. In this lab you will experiment with two Priority Queue implementations, one based on Java's PriorityQueue class (which uses a heap) and one based on Java's TreeMap class (which uses a red-black tree).

Relevant Files

• MinQueue.java - A minimal Priority Queue interface.
• HeapMinQueue.java - Implementation based on Java's PriorityQueue class.
• TreeMinQueue.java - Implementation based on Java's TreeMap class. YOU NEED TO IMPLEMENT THIS. (Note that this implementation will not allow duplicate priorities, since Map classes do not allow duplicate keys.)
• TreeMinQueueTest.java - Minimal JUnit tests for TreeMinQueue.java.
• PriorityQueueTimer.java - Timing code for comparing the implementations.

Instructions

1. First, complete TreeMinQueue.java and confirm that it works correctly using the provided unit tests.
2. Second, take a minute to read PriorityQueueTimer.java. Consult with your group to make predictions about which operations (if any) will be faster for the heap implementation and which will be faster for the BST implementation. Run the code to see if your predictions were correct.
3. Now, double the number of elements that will be inserted into the queue. Before you re-run the tests, consider each operation to predict how the running time will be affected. Will the per-element time increase? Will it decrease? Will it stay the same? Re-run the timing code to check your predictions.

Submission

Post your timing results to the Canvas discussion. You should discuss your results with your team members and make sure you understand them.

Based on your results, under what circumstances would a heap-based implementation be preferable to a BST-based implementation? Under what circumstances would a BST-based implementation be preferable?