CSE 373 Data Structures 11au, Homework 3

Electronic Turn-in due: 11 pm Thursday, 10/27/2011

Programming:

Implement three priority queues according to the PriorityQueue interface provided.  You should provide the following implementations:

 

Each heap implementation should be in its own file (BinaryHeap.java, ThreeHeap.java, MyPQ.java).  Implement the BinaryHeap (a binary min heap) as an array discussed in lecture.  For the ThreeHeap we suggest starting with a copy of your BinaryHeap code and making changes as necessary.  Your ThreeHeap should still follow the contiguous structure (complete tree) form of the binary min heap discussed in class. For your MyPQ implementation, feel free to get creative.  The simplest possible implementation might just use an array (sorted or unsorted), a linked list (sorted or unsorted) or a tree.  Whatever you do, be sure it implements the PriorityQueue interface provided, and does not use parts of the Java collections framework.  Your priority queues only need to work with doubles. 

 

Your priority queues should allow duplicates.  That is, two or more copies of the same value should be allowed to exist in the heap at the same time.  For example when you call deletemin and you have say {3, 3, 6, 7} in the heap, it would just return one of the 3's, then on the next deletemin it would return the other 3. It does not matter which 3 is returned first. This corresponds to a "tie" in priority - like two print jobs of the same size. According to our definition of priority queue, the only thing that must be guaranteed is that all the 3's will be returned before a 6 or 7 would be returned, and that the 6 would be returned before the 7.

 

Your implementations should automatically grow (if interested you may also make them shrink - this is optional) as necessary.  Note: Growing an array implementation one element at a time is not likely to be the most time efficient solution, and you should NOT use Java class libraries (no import statements).

 

Provided code:

We will be testing the code that you submit - so we will expect that you have done the same!  (We will also be asking you to turn in your testing code.)

Grading: For this assignment we will be grading more strictly for things like style and efficiency than we did on HW #1. Although for your MyPQ implementation again, something as simple as an array or a linked list is fine – we are not grading it based on how efficient it is in terms of choice of underlying data structure.

 

Write-up Questions:

This week your write-up involves a comparison of your three heap implementations.  I would expect these reports to be a couple of pages long, potentially longer if you include many graphs or tables.  Exceptional reports may be awarded a small amount of extra credit, so have fun with this!  Please prepare a report that addresses the following:

  1. Big-O Analysis: What is the worst case big-O running time of isEmpty, size, insert, findMin, and deletemin operations on all three of your heap implementations (Binary Min Heap, ThreeHeap, MyPQ).
  2. Timing your code: Perform several timing experiments (similar to what you did in homework #2, where you timed pieces of code), to examine the running time of all three of your heap implementations.  An experiment will include running the same client code (that uses a Priority Queue) for your three different heap implementations *for at least four different values of N* and timing this.  It is up to you to write and to determine what this client code should be.  Just be sure that it exercises your insert and deletemin operations “in a reasonable manner” – reasonable here means eventually deleting everything that has been inserted into the heap.  You are not required to explicitly measure calls to findMin, size, and isEmpty but feel free to do so if interested.  Similar to homework #2, graphing your results is recommended, but a table of results will work also. Please note that similar to HW #2, you are required to turn in the code you used to do your timing experiments.
  3. Comparison: Compare what you see in your experiments, to what you expected to see based on a big-O analysis.  (This is similar to what you should have done in homework #2 as well.)  In your discussion you should answer these questions:
    1. How useful was big-O for predicting the measured run time of insert and deletemin for your three implementations? 
    2. If your predictions based on Big-O differed substantially from your measured times, speculate as to why this occurred.
    3. Which of your three implementations would you recommend to someone who needs to use a heap?  Why is that one preferred?  Are there any conditions under which you might suggest using your other implementations?
  4. Testing: Please briefly discuss how you went about testing your three heap implementations.  Feel free to refer to your submitted test files.

 

What to turn in:

Electronic Turn-in should include the following files:

 

Above and Beyond:

There are no explicit above and beyond options for this assignment, but exceptional reports may receive small amounts of extra credit.  You might also consider implementing several different heaps from very simple to very complex (the book discusses Leftist, Skew, Binomial Queues, and Fibonacci).  If you implement other heaps and discuss them in your report, please include the Java code for those heaps as well.  The file named MyPQ.java is the one that will be graded as part of the original assignment.